Spiral Matrix — Layer-by-Layer Traversal
Maintain four boundaries (top, bottom, left, right) and peel layers while updating them carefully.
Problem Statement
Return all elements of an m × n matrix in spiral order.
Why This Problem Matters
- Tests control of loop invariants and boundary updates.
- Useful warm-up for harder matrix traversal questions.
- Highlights the importance of handling edge cases for rectangular matrices.
Thought Process
Track shrinking bounds
top, bottom, left, and right pointers describe the current layer; after traversing a side, move the corresponding boundary inward.
Avoid duplicates in single-row/column cases
Check bounds before traversing vertical segments to ensure there is still area left.
Collect results sequentially
Push elements into a list as you traverse; no additional data structures required.
Step-by-Step Reasoning
- While top <= bottom and left <= right, traverse top row left→right then increment top.
- Traverse right column top→bottom then decrement right.
- If top <= bottom, traverse bottom row right→left and decrement bottom.
- If left <= right, traverse left column bottom→top and increment left.
Dry Run
3×3 matrix
Collect [1,2,3,6,9,8,7,4,5] following the boundary updates.
Single column matrix
Top <= bottom check prevents traversing bottom row twice.
Complexity Analysis
Time
O(m·n)
Space
O(1)
Why
Each element visited exactly once; only boundary variables used.
Annotated Solution
import java.util.ArrayList;
import java.util.List;
public class SpiralMatrix {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> output = new ArrayList<>();
if (matrix.length == 0) {
return output;
}
int top = 0;
int bottom = matrix.length - 1;
int left = 0;
int right = matrix[0].length - 1;
while (top <= bottom && left <= right) {
for (int col = left; col <= right; col += 1) {
output.add(matrix[top][col]);
}
top += 1;
for (int row = top; row <= bottom; row += 1) {
output.add(matrix[row][right]);
}
right -= 1;
if (top <= bottom) {
for (int col = right; col >= left; col -= 1) {
output.add(matrix[bottom][col]);
}
bottom -= 1;
}
if (left <= right) {
for (int row = bottom; row >= top; row -= 1) {
output.add(matrix[row][left]);
}
left += 1;
}
}
return output;
}
}Boundary pointers control which layer we traverse next, ensuring each element appears exactly once.
Common Pitfalls
- Forgetting boundary checks causes duplicates when matrix degenerates to one row or column.
- Incorrect order of boundary updates can skip elements.
- Infinite loops occur if you fail to move all four boundaries.
Follow-Up Questions
- How would you fill a matrix in spiral order instead of reading it?
- Can you adapt this to spiral outward from the centre?