TL;DR
Walk four shrinking boundaries (top/bottom/left/right) inward — O(m·n) time, O(1) extra space beyond the output.
Approach 1 — Direction simulation with a visited grid
Walk the spiral one step at a time. Move in the current direction (right → down → left → up, cycling) and turn clockwise whenever the next cell is off the grid or already seen. A boolean visited grid records which cells are consumed.
from typing import List
def spiralOrder(matrix: List[List[int]]) -> List[int]:
m, n = len(matrix), len(matrix[0])
visited = [[False] * n for _ in range(m)]
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] # R, D, L, U
r = c = d = 0
result = []
for _ in range(m * n):
result.append(matrix[r][c])
visited[r][c] = True
nr, nc = r + directions[d][0], c + directions[d][1]
if 0 <= nr < m and 0 <= nc < n and not visited[nr][nc]:
r, c = nr, nc
else:
d = (d + 1) % 4 # turn clockwise
r += directions[d][0]
c += directions[d][1]
return result
Complexity: O(m·n) time, O(m·n) extra space for visited. Simple, but it allocates a second grid.
Approach 2 — Four shrinking boundaries (O(1) space)
The visited grid is unnecessary: the four edges of the not-yet-emitted rectangle already hold the state. Keep top, bottom, left, right; emit the top row and drop it (top += 1), emit the right column and drop it (right -= 1), and so on. Re-check the loop condition between passes so a final lone row or column isn’t traversed twice.
from typing import List
def spiralOrder(matrix: List[List[int]]) -> List[int]:
m, n = len(matrix), len(matrix[0])
top, bottom, left, right = 0, m - 1, 0, n - 1
result = []
while top <= bottom and left <= right:
for c in range(left, right + 1): # top row, left → right
result.append(matrix[top][c])
top += 1
for r in range(top, bottom + 1): # right column, top → bottom
result.append(matrix[r][right])
right -= 1
if top <= bottom: # bottom row, right → left
for c in range(right, left - 1, -1):
result.append(matrix[bottom][c])
bottom -= 1
if left <= right: # left column, bottom → top
for r in range(bottom, top - 1, -1):
result.append(matrix[r][left])
left += 1
return result
Walkthrough with [[1,2,3,4],[5,6,7,8],[9,10,11,12]] (top=0,bottom=2,left=0,right=3):
- Top row
1,2,3,4 → top=1.
- Right column (rows 1..2, col 3)
8,12 → right=2.
top(1) <= bottom(2): bottom row (cols 2..0) 11,10,9 → bottom=1.left(0) <= right(2): left column (rows 1..1, col 0) 5 → left=1.- Loop again (
top=1<=bottom=1, left=1<=right=2): top row (cols 1..2) 6,7 → top=2.
- Right column: range
top(2)..bottom(1) empty → right=1.
top(2) <= bottom(1) false, skip the bottom row.left(1) <= right(1) true, but the left-column range bottom(1)..top(1) is empty, so nothing is emitted → left=2.- Loop check
top(2) <= bottom(1) fails, so the outer loop ends.
- Result:
[1,2,3,4,8,12,11,10,9,5,6,7]. Matches.
Complexity: O(m·n) time, O(1) extra space beyond the returned list.
Common pitfalls
- Omitting the
if top <= bottom / if left <= right guards before the bottom row and left column — on a single leftover row or column you’d emit it twice.
- Off-by-one in the reversed ranges: bottom row goes
range(right, left - 1, -1); the -1 bounds are easy to botch.
- Assuming a square matrix —
m and n differ, so never reuse one dimension for both.
- Updating a boundary at the wrong time (before emitting its edge instead of after).
Pattern takeaway
For layered grid traversals, represent the frontier with a handful of boundary indices and shrink them as you consume each edge — no auxiliary grid needed. The recurring guard is to re-test the loop condition between the horizontal and vertical passes, since the innermost layer can degenerate to a single line.