Problem. Given an m × n matrix, return its elements in spiral order: clockwise from the top-left, moving inwards.
1 2 3 4
5 6 7 8 → [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]
9 10 11 12
ML context. This is the cleanest exercise in traversal order over a 2D grid, which matters whenever layout meets computation: tiled matrix multiplication, patch extraction for vision transformers, space-filling orders for cache-friendly access, and reading feature maps layer by layer. The real skill tested is boundary bookkeeping: getting the edges exactly right.
There's no faster algorithm to find: every cell must be read once, so O(m · n) is optimal. The lesson is about memory and correctness.
1. Step 1: Clarify
| Question | Answer | Why it matters |
|---|---|---|
| Rectangular? | Yes, m × n, possibly 1 × n or m × 1 | Single rows and columns are the bug magnets |
| Empty matrix? | Possible | Return [] |
| Modify the input? | No | Rules out marking visited cells inside it |
| Size? | Up to 10 × 10 here, 10⁴ × 10⁴ in general | Decides whether O(m · n) extra memory is acceptable |
2. Step 2: Brute force: simulate with a visited grid
Walk like a robot: go right until you'd hit a wall or a visited cell, then turn clockwise. A separate visited grid
remembers where you've been.
def spiral_visited(m):
if not m or not m[0]:
return []
rows, cols = len(m), len(m[0])
visited = [[False] * cols for _ in range(rows)] # O(m · n) extra
dr, dc = [0, 1, 0, -1], [1, 0, -1, 0] # right, down, left, up
r = c = d = 0
out = []
for _ in range(rows * cols):
out.append(m[r][c])
visited[r][c] = True
nr, nc = r + dr[d], c + dc[d]
if not (0 <= nr < rows and 0 <= nc < cols) or visited[nr][nc]:
d = (d + 1) % 4 # turn clockwise
nr, nc = r + dr[d], c + dc[d]
r, c = nr, nc
return out
M = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]
assert spiral_visited(M) == [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]
assert spiral_visited([[1, 2, 3]]) == [1, 2, 3]
assert spiral_visited([[1], [2], [3]]) == [1, 2, 3]
print("visited-grid walk works: O(m · n) time, O(m · n) extra space")
O(m · n) time is already optimal. But the visited grid costs O(m · n) extra memory: a 10⁴ × 10⁴ boolean grid
is 100 million entries. Can we know where the walls are without remembering every cell?
3. Step 3: Optimise: four shrinking boundaries
First principles. The visited cells always form complete outer rows and columns. So the unvisited region is
always a rectangle, described by just four numbers: top, bottom, left, right. Read one side, then move
that boundary inwards.
import random
def spiral(m):
if not m or not m[0]:
return []
top, bottom, left, right = 0, len(m) - 1, 0, len(m[0]) - 1
out = []
while top <= bottom and left <= right:
for c in range(left, right + 1): # top row →
out.append(m[top][c])
top += 1
for r in range(top, bottom + 1): # right column ↓
out.append(m[r][right])
right -= 1
if top <= bottom: # guard: a row is left
for c in range(right, left - 1, -1): # bottom row ←
out.append(m[bottom][c])
bottom -= 1
if left <= right: # guard: a column is left
for r in range(bottom, top - 1, -1): # left column ↑
out.append(m[r][left])
left += 1
return out
def spiral_visited(m):
if not m or not m[0]:
return []
rows, cols = len(m), len(m[0])
seen = [[False] * cols for _ in range(rows)]
dr, dc = [0, 1, 0, -1], [1, 0, -1, 0]
r = c = d = 0
out = []
for _ in range(rows * cols):
out.append(m[r][c])
seen[r][c] = True
nr, nc = r + dr[d], c + dc[d]
if not (0 <= nr < rows and 0 <= nc < cols) or seen[nr][nc]:
d = (d + 1) % 4
nr, nc = r + dr[d], c + dc[d]
r, c = nr, nc
return out
M = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]
assert spiral(M) == [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]
rng = random.Random(26)
for _ in range(500):
rows, cols = rng.randint(1, 6), rng.randint(1, 6)
m = [[r * cols + c for c in range(cols)] for r in range(rows)]
assert spiral(m) == spiral_visited(m)
assert sorted(spiral(m)) == list(range(rows * cols)) # every cell exactly once
print("four boundaries: O(m · n) time, O(1) extra, matches the walk on 500 shapes")
- Time: O(m · n): each cell is read once. Extra space: O(1) (besides the output).
- Why the two guards: after reading the top row and right column, the remaining rectangle may be empty. For a
single row like
[[1, 2, 3]], without thetop <= bottomcheck the "bottom row ←" loop would read 3, 2, 1 again.
Quick check
What goes wrong on a single-row matrix [[1, 2, 3]] if you drop the top <= bottom guard?
Show the answer
B. After reading the top row, top > bottom, but the bottom-row loop still runs and reads the same row backwards, giving duplicates — The guard checks that a distinct bottom row still exists before reading it.
4. When the constraints change
| If the constraint becomes… | Best approach | Time | Extra space |
|---|---|---|---|
| Classic read-out | Four shrinking boundaries | O(m·n) | O(1) |
| Simplest to get right under pressure | Direction-turning walk with a visited grid | O(m·n) | O(m·n) |
| May modify the input | Walk and mark visited cells with a sentinel | O(m·n) | O(1) |
| Generate an n × n spiral of 1..n² | Same boundaries, writing instead of reading | O(n²) | O(n²) output |
| Counter-clockwise or another start corner | Same idea, different side order | O(m·n) | O(1) |
| Only the k-th element | Skip whole layers: each layer has 2(h + w) − 4 cells | O(min(m, n)) | O(1) |
Change A: generate a spiral instead of reading one
The same four boundaries, but now write 1, 2, 3, … into an empty grid. Reading and writing are the same traversal: once the order is right, the action at each cell is just a detail.
def generate_spiral(n):
m = [[0] * n for _ in range(n)]
top, bottom, left, right = 0, n - 1, 0, n - 1
k = 1
while top <= bottom and left <= right:
for c in range(left, right + 1):
m[top][c] = k; k += 1
top += 1
for r in range(top, bottom + 1):
m[r][right] = k; k += 1
right -= 1
if top <= bottom:
for c in range(right, left - 1, -1):
m[bottom][c] = k; k += 1
bottom -= 1
if left <= right:
for r in range(bottom, top - 1, -1):
m[r][left] = k; k += 1
left += 1
return m
assert generate_spiral(3) == [[1, 2, 3], [8, 9, 4], [7, 6, 5]]
assert generate_spiral(1) == [[1]]
print("generating a spiral reuses the same boundaries")
Change B: jump straight to the k-th element
Each full layer of an h × w rectangle has 2(h + w) − 4 cells (or h · w if it's a single row or column). Skip whole
layers until k falls inside one, then walk only that layer: O(min(m, n)) layer skips plus at most one layer's walk,
instead of reading everything.
Change C: diagonal or zig-zag order
Other traversal orders follow the same discipline: describe what remains with a few indices, and write the turning
rule down before coding. (A zig-zag over diagonals uses r + c = constant per diagonal.)
Quick check
What's the core idea that removes the visited grid?
Show the answer
A. The unvisited cells always form a rectangle, so four boundary indices describe exactly what's left — Because the spiral peels off whole rows and columns, the remaining region stays a rectangle.
5. Saying it out loud
"Every cell has to be read, so O(m·n) is optimal. A walk that turns at walls and visited cells works but needs an O(m·n) visited grid. Since the unvisited region is always a rectangle, I'll keep top, bottom, left and right, read one side at a time and shrink that boundary, with guards before the bottom row and left column so single rows or columns aren't read twice. O(1) extra space."
Check yourself
- Why can't spiral order be faster than O(m · n)?
- What does the visited grid cost, and what replaces it?
- Why does the unvisited region stay a rectangle?
- Which two reads need guards, and why?
- How do you generate a spiral of 1..n²?
- How many cells are in one full layer of an h × w rectangle?
Answers
- The output contains all m · n values, and each must be read.
- O(m · n) extra memory; four boundary indices describe the remaining region.
- Each pass removes a complete outer row or column.
- The bottom row (needs
top <= bottom) and the left column (needsleft <= right): after the first two sides, the remaining rectangle may be empty, and reading would repeat cells. - Run the same boundary loop, writing an increasing counter instead of reading.
2(h + w) − 4when h, w ≥ 2 (h · w for a single row or column).