Spiral Matrix
Walk a grid in a spiral using four shrinking boundaries — and see why the last two walks need a guard
Problem Statement
Return all elements of the matrix in spiral order: across the top, down the right, back along the bottom, up the left, then inward.
Input: [[1, 2, 3],
[4, 5, 6],
[7, 8, 9]]
Output: [1, 2, 3, 6, 9, 8, 7, 4, 5]
Input: [[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]Intuition
The tempting approach: track a direction, move until you hit a wall or a visited cell, then turn right. It works, but it needs a visited grid — O(n²) extra memory — and the turning logic is easy to get subtly wrong.
The insight
Do not track a direction. Track four boundaries and shrink them.
top, bottom, left, right
walk the top row left → right then top++
walk the right column top → bottom then right--
walk the bottom row right → left then bottom--
walk the left column bottom → top then left++Each walk consumes an entire edge, then that edge is removed from consideration by moving its boundary inward. The boundaries close in, and the loop ends when they cross.
No visited grid, no direction variable, O(1) extra space.
The spiral is not a clever traversal — it is four straightforward walks, repeated on a shrinking rectangle.
The Guard That Everyone Misses
After the first two walks, the rectangle may have collapsed to a single row or column. Walking back along it would emit the same values a second time.
Single row [1, 2, 3]:
top row → 1, 2, 3 top becomes 1, bottom is still 0
right column → nothing (top > bottom)
bottom row → 3, 2, 1 WRONG — re-emits the same row backwardsCheck the boundaries again before the last two walks
if top <= bottom: walk the bottom row
if left <= right: walk the left columnThe first two walks need no guard, because the while condition already validated the rectangle. But top++ and right-- happen inside the iteration, so by the time the third and fourth walks run, the rectangle may no longer exist.
Symptom: extra elements in the output, only on inputs with a single row or column, or an odd-sized centre.
Approach
While top <= bottom and left <= right, do four walks
Top row rightwards, right column downwards, bottom row leftwards, left column upwards.
Guard the third and fourth walks
The rectangle may have collapsed since the loop condition was checked.
[1, 2, 3]Solution
def spiral_order(matrix: list[list[int]]) -> list[int]:
"""Return the matrix elements in spiral order."""
if not matrix or not matrix[0]:
return []
result: list[int] = []
top, bottom = 0, len(matrix) - 1
left, right = 0, len(matrix[0]) - 1
while top <= bottom and left <= right:
for c in range(left, right + 1):
result.append(matrix[top][c])
top += 1
for r in range(top, bottom + 1):
result.append(matrix[r][right])
right -= 1
# The rectangle may have collapsed since the while check.
if top <= bottom:
for c in range(right, left - 1, -1):
result.append(matrix[bottom][c])
bottom -= 1
if left <= right:
for r in range(bottom, top - 1, -1):
result.append(matrix[r][left])
left += 1
return resultComplexity Analysis
Time Complexity
O(rows × cols)
Space Complexity
O(1)
Time — every cell is appended exactly once. That is optimal, since all of them appear in the output.
Space — four integers. The output does not count as extra space, since it is what was asked for. Compare with the direction-tracking version, which needs an O(rows × cols) visited grid.
Edge Cases
Related Problems
- Rotate Image — another in-place grid transform built from simple steps
- Transpose Matrix — the index arithmetic underneath
- Matrix — the boundary technique in general