How Do You Traverse a Matrix in Spiral Order?
Learn the four-boundary technique for spiral matrix traversal, the classic narrow-matrix bug, and how to answer this interview question.
Expected Interview Answer
Spiral matrix traversal visits every element by tracking four shrinking boundaries — top, bottom, left, right — and walking right across the top row, down the right column, left across the bottom row, and up the left column, shrinking each boundary after its pass, in O(rows * cols) time and O(1) extra space beyond the output.
After completing each of the four directional walks, the corresponding boundary moves inward: top increments, right decrements, bottom decrements, left increments. The loop continues while top <= bottom and left <= right, and boundary checks must be re-verified after the right-walk and after the down-walk to avoid revisiting a row or column already consumed, which is the most common source of bugs. This pattern generalizes beyond square matrices to any m x n matrix. The technique is a direct analogue of peeling layers off an onion, one ring at a time from the outside in.
- Visits every element exactly once in O(rows * cols) time
- O(1) extra space beyond the output list
- Works uniformly for square and rectangular matrices
- Boundary-shrinking is easy to verify and debug incrementally
AI Mentor Explanation
Spiral traversal is like a ground-staff crew mowing a rectangular pitch outer-ring first: they mow left to right along the top edge, then top to bottom along the right edge, then right to left along the bottom edge, then bottom to top along the left edge, before starting the next inner ring. After finishing each edge, that boundary shrinks inward so the crew never re-mows a strip they already covered. The crew must re-check whether a ring still exists before starting each new edge, since a very narrow rectangle can run out of rows or columns mid-ring. This layer-by-layer peeling covers the whole ground exactly once, using no extra field to work from.
Step-by-Step Explanation
Step 1
Initialize four boundaries
Set top=0, bottom=rows-1, left=0, right=cols-1.
Step 2
Walk right, then down
Traverse left→right along the top row, incrementing top; then top→bottom along the right column, decrementing right.
Step 3
Re-check before walking left and up
If top <= bottom, traverse right→left along the bottom row and decrement bottom; if left <= right, traverse bottom→top along the left column and increment left.
Step 4
Repeat while boundaries are valid
Continue the four-direction cycle while top <= bottom and left <= right, shrinking boundaries each pass.
What Interviewer Expects
- Correctly describe the four-boundary shrinking technique
- Identify the classic bug: forgetting to re-check boundaries before the third and fourth legs
- State O(rows * cols) time and O(1) extra space (excluding output)
- Handle edge cases: single row, single column, empty matrix
Common Mistakes
- Not re-validating top <= bottom and left <= right before the bottom-row and left-column passes, causing duplicate visits on narrow matrices
- Off-by-one errors when incrementing/decrementing boundaries
- Assuming the matrix must be square when it can be any m x n shape
- Forgetting to handle a single row or single column matrix as a special case
Best Answer (HR Friendly)
“To traverse a matrix in spiral order, I track four shrinking boundaries for top, bottom, left, and right, and walk right, down, left, then up around the current ring before shrinking inward to the next ring. The trickiest part is re-checking that a ring still has rows or columns left before doing the bottom and left passes, otherwise you can double-visit or skip elements on narrow matrices.”
Code Example
def spiral_order(matrix):
if not matrix or not matrix[0]:
return []
result = []
top, bottom = 0, len(matrix) - 1
left, right = 0, len(matrix[0]) - 1
while top <= bottom and left <= right:
for col in range(left, right + 1):
result.append(matrix[top][col])
top += 1
for row in range(top, bottom + 1):
result.append(matrix[row][right])
right -= 1
if top <= bottom:
for col in range(right, left - 1, -1):
result.append(matrix[bottom][col])
bottom -= 1
if left <= right:
for row in range(bottom, top - 1, -1):
result.append(matrix[row][left])
left += 1
return result
m = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(spiral_order(m)) # [1, 2, 3, 6, 9, 8, 7, 4, 5]Follow-up Questions
- How would you generate a spiral matrix given only its dimensions, filling in order 1..n²?
- How would you traverse the matrix in spiral order starting from the center outward instead?
- How does the algorithm change for a matrix with more rows than columns, or vice versa?
- How would you unit test this to catch the narrow-matrix boundary bug?
MCQ Practice
1. What is the most common bug in spiral matrix traversal implementations?
Without re-validating top <= bottom and left <= right before the last two legs, narrow matrices get elements double-visited or skipped.
2. What is the time complexity of spiral matrix traversal on an m x n matrix?
Every cell is visited exactly once across all four boundary passes, giving O(m * n) time.
3. Which four variables are typically tracked to perform spiral traversal?
The four shrinking boundaries top, bottom, left, and right define the current unvisited ring of the matrix.
Flash Cards
What four boundaries does spiral traversal track? — top, bottom, left, right, each shrinking inward after its directional pass.
What order does spiral traversal visit directions in? — Right along the top, down the right, left along the bottom, up the left, then repeat inward.
What is the classic spiral traversal bug? — Not re-checking shrunk boundaries before the third and fourth legs, causing double-visits or skips on narrow matrices.
What is the time complexity of spiral traversal? — O(rows * cols), since every element is visited exactly once.