[LeetCode] 54. Spiral Matrix

Posted on | In

Problem

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

Example 1:

1
2
3
4
5
6
7
Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]

Example 2:

1
2
3
4
5
6
7
Input:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

Explanation

  1. Similar to (48. Rotate Image ), from the above example2, we can think of four groups: [1, 2, 3], [4, 8], [12, 11, 10], [9, 5]. Then, we define the top, right, bottom, left. While top < bottom && left < right, then we loop through each group and add the number to res.

  2. Out of the loop, it’s either top > bottom && left > right, then we are done. Else if top == bottom && left < right, from the above example2, this will be one horizontal row [6, 7] we havn’t added to the res. Else if left == right && top < bottom, this will be one vertical column, then we can add those numbers. Finally, we are done.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        if (matrix == null || matrix.length == 0) return res;
        
        int top = 0;
        int right = matrix[0].length-1;
        int bottom = matrix.length-1;
        int left = 0;
        
        while (top < bottom && left < right) {
            for (int i = left; i < right; i++) {
                res.add(matrix[top][i]);
            }
            for (int i = top; i < bottom; i++) {
                res.add(matrix[i][right]);
            }
            for (int i = right; i > left; i--) {
                res.add(matrix[bottom][i]);
            }
            for (int i = bottom; i > top; i--) {
                res.add(matrix[i][left]);
            }
            top++;
            right--;
            bottom--;
            left++;
        }
        if (top == bottom) {
            for (int i = left; i <= right; i++) {
                res.add(matrix[top][i]);
            }
        } else if (left == right) {
            for (int i = top; i <= bottom; i++) {
                res.add(matrix[i][left]);
            }
        }
        
        return res;
    }
}