# Solution by awice

• #### 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++) {
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 in `ans`.

#### Approach #2: Layer-by-Layer [Accepted]

Intuition

The answer will be all the elements in clockwise order from the first-outer layer, followed by the elements from the second-outer 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 first-outer layer equal to 1, all elements in the second-outer layer equal to 2, and all elements in the third-outer 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 top-left coordinates `(r1, c1)` and bottom-right 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`.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.