54. Spiral Matrix
Model: qwen3.5:9b
Topics: Array
FAANG asked: 1
Acceptance rate: 36.5%
Problem Breakdown
The goal is to traverse a 2D matrix in a clockwise spiral pattern, starting from the top-left corner and moving right. We need to return all elements as a single flattened list.
Inputs: A rectangular m x n integer matrix (List[List[int]]).
Outputs: A flat List[int].
Constraints & Edge Cases:
- Dimensions are at least 1x1 (no empty matrices per constraints, but logic should handle it).
- Values can be negative.
- The tricky part is managing the boundaries so we don’t re-traverse rows or columns that have already been visited, especially when
mequalsn, or in single-row/column cases where top/bottom and left/right indices might overlap.
Intuition
A naive approach would try to simulate movement with a direction vector (Right -> Down -> Left -> Up) using coordinates (r, c) and changing directions upon hitting boundaries. While valid, this requires tracking visited cells or complex boundary conditions for each turn.
The stronger insight is Boundary Shrinkage. Instead of moving step-by-step through the grid, we treat the matrix as a shrinking rectangle defined by four indices: top, bottom, left, and right.
- Traverse from left to right along the top row, then increment
top(consume that row). - Traverse from top to bottom along the right column, then decrement
right(consume that col). - Check if boundaries crossed before traversing back: traverse right-to-left on the new bottom row, decrement
bottom. - Similarly check and traverse up the left side, increment
left.
This ensures every element is visited exactly once in time without extra space for a “visited” set.
Approach
- Initialize four boundary pointers:
top = 0,bottom = m - 1,left = 0,right = n - 1. - Use a
whileloop that continues as long as the boundaries haven’t crossed (top <= bottomandleft <= right). - Inside the loop:
- Top Row: Iterate columns from
lefttoright. Append elements, then incrementtop. - Right Column: Iterate rows from
toptobottom. Append elements, decrementright. - Bottom Row (Conditional): If boundaries still valid (
top <= bottom), iterate right-to-left. Decrementbottom. This check is crucial because if we just finished the top row and there was only one row left, incrementingtopwould make it crossbottom, so traversing again here would be redundant or wrong. - Left Column (Conditional): If boundaries still valid (
left <= right), iterate bottom-to-top. Incrementleft.
- Top Row: Iterate columns from
Complexity Analysis
- Time: . We visit every cell in the matrix exactly once during the traversal steps.
- Space: auxiliary space (excluding the output list which is required to store the result). The boundary pointers use constant extra memory.
Solution
def spiralOrder(matrix):
if not matrix:
return []
m, n = len(matrix), len(matrix[0])
top, bottom = 0, m - 1
left, right = 0, n - 1
result = []
while top <= bottom and left <= right:
# Traverse Top Row (Left -> Right)
for col in range(left, right + 1):
result.append(matrix[top][col])
top += 1
# Traverse Right Column (Top -> Bottom)
if top > bottom: break
for row in range(top, bottom + 1):
result.append(matrix[row][right])
right -= 1
# Traverse Bottom Row (Right -> Left)
if left > right: break
for col in range(right, left - 1, -1):
result.append(matrix[bottom][col])
bottom -= 1
# Traverse Left Column (Bottom -> Top)
if top > bottom: break
for row in range(bottom, top - 1, -1):
result.append(matrix[row][left])
left += 1
return result
Edge Cases Handled
- Single Row Matrix: The
topincrement happens immediately after the first pass. Subsequent checks (if top > bottom) prevent traversing a non-existent right column or bottom row again, preventing duplicates. - Single Column Matrix: Similar logic applies; horizontal passes happen once (or zero times if width is 1), vertical passes handle the rest correctly via boundary decrements/increments.
- Square Matrix (): The standard shrinking rectangle logic works perfectly without special casing for square vs rectangular grids.