Spiral Matrix

Given a matrix of_m_x_n_elements (_m_rows,_n_columns), return all elements of the matrix in spiral order.

Example 1:

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

Example 2:

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

Simulation 模拟法

1 新建一个二维数组seen[m][n]，seen[i][j]对应matrix[i][j]，遍历过的元素设为true

2 设定上下左右四个边界值，即rowLower, rowUpper, colLower, colUpper, 在转换遍历方向时增减边界值的大小

Layer-by-Layer

@LeetCode

``````int r1 = 0, r2 = matrix.length - 1;
int c1 = 0, c2 = matrix[0].length - 1;
while (r1 <= r2 && c1 <= c2) {
...
}
``````

Solution

Simulation - Setting Upper Lower Bounds ofRow, Column indexes - (3ms 10.49%)

``````class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return ans;
}
int m = matrix.length;
int n = matrix[0].length;
int total = m * n;
int row = 0, col = 0;

// lower and upper bound for row, col indexes
int rowLower = 0, rowUpper = m - 1;
int colLower = 0, colUpper = n - 1;

// direction offset for row index (dir[][0]), column index (dir[][1])
int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

// mapping of RIGHT, DOWN, LEFT, UP to indexes in dir[][]
int RIGHT = 0, DOWN = 1, LEFT = 2, UP = 3;

// initial direction
int toward = RIGHT;

for (int k = 0; k < total; k++) {

// change direction, change boundary limits when hitting boundaries
if (toward == RIGHT && col == colUpper) {
rowLower++;
toward = (toward + 1) % 4;
} else if (toward == DOWN && row == rowUpper) {
colUpper--;
toward = (toward + 1) % 4;
} else if (toward == LEFT && col == colLower) {
rowUpper--;
toward = (toward + 1) % 4;
} else if (toward == UP && row == rowLower) {
colLower++;
toward = (toward + 1) % 4;
}

row = row + dir[toward][0];
col = col + dir[toward][1];
}
return ans;
}
}
``````

Simulation - Additional auxiliary matrix `seen[][]` for visited elements

``````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++) {
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;
}
}
``````

Layer by Layer

``````class Solution {
public List < Integer > spiralOrder(int[][] matrix) {
List ans = new ArrayList();
if (matrix.length == 0)
return ans;
int r1 = 0, r2 = matrix.length - 1;
int c1 = 0, c2 = matrix[0].length - 1;
while (r1 <= r2 && c1 <= c2) {
for (int c = c1; c <= c2; c++) ans.add(matrix[r1][c]);
for (int r = r1 + 1; r <= r2; r++) ans.add(matrix[r][c2]);
if (r1 < r2 && c1 < c2) {
for (int c = c2 - 1; c > c1; c--) ans.add(matrix[r2][c]);
for (int r = r2; r > r1; r--) ans.add(matrix[r][c1]);
}
r1++;
r2--;
c1++;
c2--;
}
return ans;
}
}
``````

Reference

https://leetcode.com/articles/spiral-matrix/