Approach #1: Simulation [Accepted]
Intuition
Draw the path that the spiral makes. We know that the path should turn clockwise whenever it would otherwise go out of bounds or into a cell that was previously visited.
Algorithm
Let the array have R
rows and C
columns. seen[r][c]
denotes that the cell on the r
th row and c
th column was previously visited. Our current position is (r, c)
, facing direction di
, and we want to visit R * C
total cells.
As we move through the matrix, our candidate next position is (cr, cc)
. If the candidate is in the bounds of the matrix and unseen, then it becomes our next position; otherwise, our next position is the one after performing a clockwise turn.
Java
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;
}
}
Python
class Solution(object):
def spiralOrder(self, matrix):
if not matrix: return []
R, C = len(matrix), len(matrix[0])
seen = [[False] * C for _ in matrix]
ans = []
dr = [0, 1, 0, 1]
dc = [1, 0, 1, 0]
r = c = di = 0
for _ in range(R * C):
ans.append(matrix[r][c])
seen[r][c] = True
cr, cc = r + dr[di], c + dc[di]
if 0 <= cr < R and 0 <= cc < C and not seen[cr][cc]:
r, c = cr, cc
else:
di = (di + 1) % 4
r, c = r + dr[di], c + dc[di]
return ans
Complexity Analysis

Time Complexity: $$O(N)$$, where $$N$$ is the total number of elements in the input matrix. We add every element in the matrix to our final answer.

Space Complexity: $$O(N)$$, the information stored in
seen
and inans
.
Approach #2: LayerbyLayer [Accepted]
Intuition
The answer will be all the elements in clockwise order from the firstouter layer, followed by the elements from the secondouter layer, and so on.
Algorithm
We define the k
th outer layer of a matrix as all elements that have minimum distance to some border equal to k
. For example, the following matrix has all elements in the firstouter layer equal to 1, all elements in the secondouter layer equal to 2, and all elements in the thirdouter layer equal to 3.
[[1, 1, 1, 1, 1, 1, 1],
[1, 2, 2, 2, 2, 2, 1],
[1, 2, 3, 3, 3, 2, 1],
[1, 2, 2, 2, 2, 2, 1],
[1, 1, 1, 1, 1, 1, 1]]
For each outer layer, we want to iterate through it's elements in clockwise order starting from the top left corner. Suppose the current outer layer has topleft coordinates (r1, c1)
and bottomright coordinates (r2, c2)
.
Then, the top row is (r1, c) for c = c1 ... c2
. The rest of the right side is (r, c2) for r = r1+1 ... r2
. Then, if there are four sides to this layer (ie., r1 < r2 and c1 < c2
), we iterate through the bottom side and left side as shown in the solutions below.
Java
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;
}
}
Python
class Solution(object):
def spiralOrder(self, matrix):
def spiral_coords(r1, c1, r2, c2):
for c in range(c1, c2 + 1):
yield r1, c
for r in range(r1 + 1, r2 + 1):
yield r, c2
if r1 < r2 and c1 < c2:
for c in range(c2  1, c1, 1):
yield r2, c
for r in range(r2, r1, 1):
yield r, c1
if not matrix: return []
ans = []
r1, r2 = 0, len(matrix)  1
c1, c2 = 0, len(matrix[0])  1
while r1 <= r2 and c1 <= c2:
for r, c in spiral_coords(r1, c1, r2, c2):
ans.append(matrix[r][c])
r1 += 1; r2 = 1
c1 += 1; c2 = 1
return ans
Complexity Analysis

Time Complexity: $$O(N)$$, where $$N$$ is the total number of elements in the input matrix. We add every element in the matrix to our final answer.

Space Complexity: $$O(N)$$, the information stored in
ans
.