class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> ans = new LinkedList<Integer>();
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++) {
ans.add(matrix[row][col]);
// 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++) {
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;
}
}
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;
}
}