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:

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]`

.**Analysis:**

The problem asks for returning all elements of the matrix in spiral order. So the key of the question is to understand what is the spiral order. We may use several examples to illustrate that.

For empty array, we return empty as well.

For array [ 1, 2], the spiral order is 1, 2

For array [1]

[2], the spiral order still 1 and 2

For array 1, 2, 3

4, 5, 6

7, 8 , 9 , the spiral order is 1, 2, 3, 6, 9, 8, 7, 4, 5

For array 1, 2, 3

4, 5, 6

7, 8, 9

10, 11, 12, the spiral order is 1, 2, 3, 6, 9, 12, 11, 10, 7, 4, 5, 8

From the above examples, we could see that the traverse order is to scan the out-most elements, then inner, and inner until we go through all the elements in the matrix.

**Solution:**

**Code (Java):**

public class Solution { public ArrayList<Integer> spiralOrder(int[][] matrix) { ArrayList<Integer> result = new ArrayList<Integer>(); // if matrix is null or empty if (matrix == null || matrix.length == 0) return result; int m = matrix.length; int n = matrix[0].length; int row = 0; int col = 0; // Handle the circle while (m > 0 & n > 0) { // For matrix has only 1 row if (m == 1) { for (int i = 0; i < n; i++) { result.add(matrix[row][col++]); } break; } else if (n == 1) { for (int i = 0; i < m; i++) { result.add(matrix[row++][col]); } break; } // move right for (int i = 0; i < n - 1; i++) { result.add(matrix[row][col++]); } // move down for (int i = 0; i < m - 1; i++) { result.add(matrix[row++][col]); } // move left for (int i = 0; i < n - 1; i++) { result.add(matrix[row][col--]); } // move up for (int i = 0; i < m - 1; i++) { result.add(matrix[row--][col]); } // move to the inner circle row++; col++; m -= 2; n -= 2; } return result; } }

**Discussion:**

Note that in the while loop we must first handle if the matrix has only one row or column left. Why was that? That is because otherwise we will generate repeated numbers. For instance, for the matrix 1, 2, 3. If we don't copy the 1, 2, 3 out and stop, we will output 1, 2, 3, 2, 1.

The time complexity of this solution is O(m * n) which is linear to the size of matrix.

**Summary:**

The problem itself is not hard to understand. But the implementation is very tricky. Make sure you understand the ideas of the implementation of the this question.

## No comments:

## Post a Comment