LeetCode - Spiral Matrix
Problem description
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]
Analysis
The initial thought is to use four direction to add item into list. And use border to make sure don’t add duplicate items. Here’s the code:
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
import java.util.ArrayList;
import java.util.List;
public class SpiralMatrix {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> res = new ArrayList<>();
if (matrix == null || matrix.length == 0 || matrix[0].length == 0){
return res;
}
int top = -1, left = -1, right = matrix[0].length, bottom = matrix.length;
int i = 0, j = 0;
int dir = 1;// 1 from left to right, 2 top ot bottom, 3 right to left, 4 bottom to top
while (res.size() < matrix.length * matrix[0].length){
res.add(matrix[i][j]);
if (dir == 1){
j++;
}
else if (dir == 2){
i++;
}
else if(dir == 3){
j--;
}
else if (dir == 4){
i--;
}
if (j == right){
top++;
j--;
i++;
dir = 2;
}
else if (i == bottom){
right--;
i--;
j--;
dir = 3;
}
else if (j == left){
bottom--;
j++;
i--;
dir = 4;
}
else if (i == top){
left++;
i++;
j++;
dir = 1;
}
}
return res;
}
}
An simplified solution is that:
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
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List ans = new ArrayList();
if (matrix.length == 0) return ans;
int R = matrix.length, C = matrix[0].length;
boolean[][] seen = new boolean[R][C];
int[] dr = {0, 1, 0, -1};
int[] dc = {1, 0, -1, 0};
int r = 0, c = 0, di = 0;
for (int i = 0; i < R * C; i++) {
ans.add(matrix[r][c]);
seen[r][c] = true;
int cr = r + dr[di];
int cc = c + dc[di];
if (0 <= cr && cr < R && 0 <= cc && cc < C && !seen[cr][cc]){
r = cr;
c = cc;
} else {
di = (di + 1) % 4;
r += dr[di];
c += dc[di];
}
}
return ans;
}
}