LeetCode 54 - Spiral Matrix
The problem gives an m x n matrix and asks us to return all elements in spiral order. Spiral order means we start from the top-left corner and move in a clockwise spiral pattern: 1. Traverse the top row from left to right 2. Traverse the right column from top to bottom 3.
Difficulty: 🟡 Medium
Topics: Array, Matrix, Simulation
Solution
Problem Understanding
The problem gives an m x n matrix and asks us to return all elements in spiral order.
Spiral order means we start from the top-left corner and move in a clockwise spiral pattern:
- Traverse the top row from left to right
- Traverse the right column from top to bottom
- Traverse the bottom row from right to left
- Traverse the left column from bottom to top
- Repeat the same process for the inner submatrix
For example, in this matrix:
1 2 3
4 5 6
7 8 9
we visit the numbers in this order:
1 → 2 → 3
↓
4 5 6
↑ ↓
7 ← 8 ← 9
which produces:
[1,2,3,6,9,8,7,4,5]
The input is guaranteed to be a valid rectangular matrix. Every row has the same number of columns. The constraints are small, 1 <= m, n <= 10, so performance is not difficult, but the implementation must carefully avoid revisiting elements or going out of bounds.
Several edge cases can cause bugs in a naive implementation:
- A matrix with only one row
- A matrix with only one column
- Odd-sized matrices where one center element remains at the end
- Rectangular matrices where rows and columns are different sizes
- Small matrices like
1 x 1or1 x n
The main challenge is handling boundaries correctly while shrinking the traversal area layer by layer.
Approaches
Brute Force Approach
A straightforward approach is to simulate movement through the matrix while tracking visited cells.
We can maintain:
- The current position
- The current direction
- A visited matrix
- Direction vectors for right, down, left, and up
At each step:
- Add the current element to the result
- Mark the cell as visited
- Attempt to move forward
- If the next position is invalid or already visited, rotate direction
This approach works because it explicitly simulates spiral movement exactly as described.
The downside is the extra space required for the visited matrix. Even though the constraints are small, we can do better because the traversal naturally forms shrinking boundaries.
Optimal Approach
The key observation is that spiral traversal always operates on the current outer rectangle of the matrix.
Instead of tracking visited cells, we maintain four boundaries:
topbottomleftright
Each traversal consumes one side of the current rectangle:
- Traverse top row, then increment
top - Traverse right column, then decrement
right - Traverse bottom row, then decrement
bottom - Traverse left column, then increment
left
As the boundaries shrink inward, we eventually process the entire matrix.
This avoids the need for extra visited storage and keeps the implementation clean and efficient.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(m × n) | O(m × n) | Uses visited matrix and direction simulation |
| Optimal | O(m × n) | O(1) | Uses shrinking boundaries |
Algorithm Walkthrough
Optimal Boundary Simulation
- Initialize four boundary pointers:
top = 0bottom = rows - 1left = 0right = cols - 1
These define the current rectangle that still needs processing. 2. Create an empty result list.
This will store elements in spiral order. 3. Traverse the top row from left to right.
Iterate from left to right and append:
matrix[top][col]
After finishing, increment top because that row has been fully processed.
4. Traverse the right column from top to bottom.
Iterate from top to bottom and append:
matrix[row][right]
After finishing, decrement right.
5. Check whether rows still remain.
Sometimes the matrix has only one remaining row. Without this check, we may duplicate elements.
If top <= bottom, traverse the bottom row from right to left.
6. Traverse the bottom row from right to left.
Iterate from right down to left and append:
matrix[bottom][col]
After finishing, decrement bottom.
7. Check whether columns still remain.
Sometimes only one column remains. Without this check, elements may be duplicated.
If left <= right, traverse the left column from bottom to top.
8. Traverse the left column from bottom to top.
Iterate from bottom down to top and append:
matrix[row][left]
After finishing, increment left.
9. Repeat until boundaries cross.
The loop continues while:
top <= bottom and left <= right
Why it works
At every iteration, the algorithm processes exactly one outer layer of the remaining submatrix. After traversing a side, its boundary moves inward, guaranteeing that no element is visited twice. The loop stops once the boundaries cross, which means every valid cell has been processed exactly once.
Python Solution
from typing import List
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
rows = len(matrix)
cols = len(matrix[0])
top = 0
bottom = rows - 1
left = 0
right = cols - 1
result = []
while top <= bottom and left <= right:
# Traverse top row
for col in range(left, right + 1):
result.append(matrix[top][col])
top += 1
# Traverse right column
for row in range(top, bottom + 1):
result.append(matrix[row][right])
right -= 1
# Traverse bottom row
if top <= bottom:
for col in range(right, left - 1, -1):
result.append(matrix[bottom][col])
bottom -= 1
# Traverse left column
if left <= right:
for row in range(bottom, top - 1, -1):
result.append(matrix[row][left])
left += 1
return result
The implementation directly follows the boundary-based algorithm.
The variables top, bottom, left, and right define the remaining rectangle. Each loop iteration processes one layer of that rectangle.
The first loop traverses the top row. After processing it, top moves downward because that row is finished.
The second loop traverses the right column. After processing it, right moves leftward.
The third traversal is guarded by if top <= bottom. This prevents duplicate processing when no rows remain.
The fourth traversal is guarded by if left <= right. This prevents duplicate processing when no columns remain.
The loop terminates once all layers have been consumed.
Go Solution
func spiralOrder(matrix [][]int) []int {
rows := len(matrix)
cols := len(matrix[0])
top := 0
bottom := rows - 1
left := 0
right := cols - 1
result := []int{}
for top <= bottom && left <= right {
// Traverse top row
for col := left; col <= right; col++ {
result = append(result, matrix[top][col])
}
top++
// Traverse right column
for row := top; row <= bottom; row++ {
result = append(result, matrix[row][right])
}
right--
// Traverse bottom row
if top <= bottom {
for col := right; col >= left; col-- {
result = append(result, matrix[bottom][col])
}
bottom--
}
// Traverse left column
if left <= right {
for row := bottom; row >= top; row-- {
result = append(result, matrix[row][left])
}
left++
}
}
return result
}
The Go implementation mirrors the Python solution closely.
Slices are used for the result container, and append dynamically grows the slice as elements are added.
No special handling for integer overflow is needed because matrix values are small. The problem also guarantees that the matrix is non-empty, so accessing matrix[0] is safe.
Worked Examples
Example 1
Input:
[
[1,2,3],
[4,5,6],
[7,8,9]
]
Initial state:
| Variable | Value |
|---|---|
| top | 0 |
| bottom | 2 |
| left | 0 |
| right | 2 |
| result | [] |
First Layer
Traverse top row:
1, 2, 3
Result:
[1,2,3]
Update:
top = 1
Traverse right column:
6, 9
Result:
[1,2,3,6,9]
Update:
right = 1
Traverse bottom row:
8, 7
Result:
[1,2,3,6,9,8,7]
Update:
bottom = 1
Traverse left column:
4
Result:
[1,2,3,6,9,8,7,4]
Update:
left = 1
Second Layer
Current boundaries:
| Variable | Value |
|---|---|
| top | 1 |
| bottom | 1 |
| left | 1 |
| right | 1 |
Traverse top row:
5
Result:
[1,2,3,6,9,8,7,4,5]
Traversal complete.
Example 2
Input:
[
[1,2,3,4],
[5,6,7,8],
[9,10,11,12]
]
Initial state:
| Variable | Value |
|---|---|
| top | 0 |
| bottom | 2 |
| left | 0 |
| right | 3 |
First Layer
Top row:
1,2,3,4
Result:
[1,2,3,4]
Right column:
8,12
Result:
[1,2,3,4,8,12]
Bottom row:
11,10,9
Result:
[1,2,3,4,8,12,11,10,9]
Left column:
5
Result:
[1,2,3,4,8,12,11,10,9,5]
Second Layer
Remaining submatrix:
6 7
Top row traversal:
6,7
Final result:
[1,2,3,4,8,12,11,10,9,5,6,7]
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(m × n) | Every matrix element is visited exactly once |
| Space | O(1) | Only boundary variables are used, excluding output |
The algorithm processes each cell exactly one time during spiral traversal. No nested repeated work occurs beyond visiting every element once.
The extra space usage is constant because only four boundary pointers and a few loop variables are maintained. The output list itself is not counted in auxiliary space complexity.
Test Cases
from typing import List
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
rows = len(matrix)
cols = len(matrix[0])
top = 0
bottom = rows - 1
left = 0
right = cols - 1
result = []
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
solution = Solution()
assert solution.spiralOrder([[1]]) == [1] # Single element matrix
assert solution.spiralOrder([[1, 2, 3]]) == [1, 2, 3] # Single row
assert solution.spiralOrder([[1], [2], [3]]) == [1, 2, 3] # Single column
assert solution.spiralOrder([
[1, 2],
[3, 4]
]) == [1, 2, 4, 3] # Small square matrix
assert solution.spiralOrder([
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]) == [1, 2, 3, 6, 9, 8, 7, 4, 5] # Odd-sized square matrix
assert solution.spiralOrder([
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12]
]) == [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7] # Rectangular matrix
assert solution.spiralOrder([
[1, 2, 3, 4]
]) == [1, 2, 3, 4] # One row rectangle
assert solution.spiralOrder([
[1],
[2],
[3],
[4]
]) == [1, 2, 3, 4] # One column rectangle
assert solution.spiralOrder([
[1, 2],
[3, 4],
[5, 6]
]) == [1, 2, 4, 6, 5, 3] # Tall rectangle
assert solution.spiralOrder([
[1, 2, 3],
[4, 5, 6]
]) == [1, 2, 3, 6, 5, 4] # Wide rectangle
| Test | Why |
|---|---|
[[1]] |
Validates smallest possible matrix |
[[1,2,3]] |
Tests single row handling |
[[1],[2],[3]] |
Tests single column handling |
[[1,2],[3,4]] |
Tests small square traversal |
3 x 3 matrix |
Tests odd-sized square with center element |
3 x 4 matrix |
Tests rectangular traversal |
| One row rectangle | Ensures no duplicate bottom traversal |
| One column rectangle | Ensures no duplicate left traversal |
| Tall rectangle | Tests uneven dimensions |
| Wide rectangle | Tests different row and column counts |
Edge Cases
Single Row Matrix
A matrix like:
[[1,2,3,4]]
can cause duplicate traversal bugs if the algorithm blindly processes top and bottom rows separately.
After traversing the top row, top becomes greater than bottom. The condition:
if top <= bottom:
prevents the bottom row traversal from executing again.
Single Column Matrix
A matrix like:
[
[1],
[2],
[3]
]
creates a similar issue for left and right column traversals.
After traversing the right column, right becomes smaller than left. The check:
if left <= right:
prevents duplicate traversal of the same column.
Odd-Sized Matrix with Center Element
A matrix like:
[
[1,2,3],
[4,5,6],
[7,8,9]
]
eventually shrinks to a single center cell.
At that point:
top == bottom
left == right
The loop still executes correctly, processing exactly one final element before the boundaries cross.
This guarantees that the center element is included once and only once.