Sunday, March 9, 2014

Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

You should return [1,2,3,6,9,8,7,4,5].

Code in JAVA:
public static ArrayList<Integer> spiralOrder(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
   return new ArrayList<Integer>();
  }
  return spiralOrder(matrix, 0, 0, matrix.length, matrix[0].length);
    }
 public static ArrayList<Integer> spiralOrder(int [][] matrix, int x, int y, int m, int n){
  ArrayList<Integer> result = new ArrayList<Integer>();
  if (m <= 0 || n <= 0) {return result;}
  if (m == 1 && n == 1) {
   result.add(matrix[x][y]);
   return result;
  }
  for(int i = 0;i < n-1;i++){
            result.add(matrix[x][y++]);
        }
        for(int i = 0;i < m-1;i++){
            result.add(matrix[x++][y]);
        }
  if (m > 1) {
   for (int i = 0; i < n - 1; i++) {
    result.add(matrix[x][y--]);
   }
  }
  if (n > 1){  
   for (int i = 0; i < m - 1; i++) {
    result.add(matrix[x--][y]);
   }
  }
  if (m == 1 || n == 1) {
   result.addAll(spiralOrder(matrix, x, y, 1, 1));
  } else {
   result.addAll(spiralOrder(matrix, x + 1, y + 1, m - 2, n - 2));
  }
  return result;

 }

No comments:

Post a Comment