Spiral Matrix (LeetCode 54)
You're given an m x n matrix. Read off every cell in spiral order and return that as one flat list.
Picture peeling the matrix like an onion: sweep across the still-unvisited top row heading right, then drop down the still-unvisited rightmost column, then sweep back across the still-unvisited bottom row heading left, then climb the still-unvisited leftmost column -- shrinking the unvisited region on each pass until every cell has been read.
Worked Examples
matrix = [[1,2,3],[4,5,6],[7,8,9]][1,2,3,6,9,8,7,4,5]matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]][1,2,3,4,8,12,11,10,9,5,6,7]⚖️Formal Constraints & Bounds
m == matrix.lengthn == matrix[i].length1 <= m, n <= 10-100 <= matrix[i][j] <= 100
Core Insight
Never track complex angles. Use 4 explicit boundary coordinates top, bottom, left, right. After sweeping along an outer edge, shrink that boundary inward (top += 1, right -= 1, bottom -= 1, left += 1) and guard horizontal/vertical sweeps with top <= bottom and left <= right.
Real-World Scenario & Production Applications
Printing a board, a seating chart or a label sheet in spiral order, starting from a corner and winding inward.
Step-by-Step Execution Trace Table
| Step | Direction | Active Boundary | Visited Cells | Appended to Result | Remaining Matrix Bounds |
|---|---|---|---|---|---|
| 1 | Right (→) | row = top (0) | (0,0), (0,1), (0,2) | [1, 2, 3] | top: 1, bottom: 2, left: 0, right: 2 |
| 2 | Down (↓) | col = right (2) | (1,2), (2,2) | [6, 9] | top: 1, bottom: 2, left: 0, right: 1 |
| 3 | Left (←) | row = bottom (2) | (2,1), (2,0) | [8, 7] | top: 1, bottom: 1, left: 0, right: 1 |
| 4 | Up (↑) | col = left (0) | (1,0) | [4] | top: 1, bottom: 1, left: 1, right: 1 |
| 5 | Right (→) | row = top (1) | (1,1) | [5] | top: 2, bottom: 1 (top > bottom -> Terminate) |
| 1 | top, bottom = 0, len(matrix) - 1 |
| 2 | left, right = 0, len(matrix[0]) - 1 |
| 3 | while top <= bottom and left <= right: |
| 4 | read the top row from left to right |
| 5 | top += 1 |
| 6 | read the right column from top to bottom |
| 7 | right -= 1 |
| 8 | if top <= bottom: |
| 9 | read the bottom row from right to left |
| 10 | bottom -= 1 |
| 11 | if left <= right: |
| 12 | read the left column from bottom to top |
| 13 | left += 1 |
| 14 | return result |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Four variables (top, bottom, left, right) mutating together in a loop is easy to lose track of — but they're all doing one very physical thing.
🧅 The Analogy: Peeling an Onion, Layer by Layer
Think of the matrix as an onion made of concentric rectangular rings. The outermost ring is the top row, right column, bottom row, and left column of the whole matrix. Once you've walked all the way around that ring, it's gone — you peel it off and you're left with a smaller onion (a smaller rectangle) sitting one layer inward. You repeat the exact same "walk the ring" move on the smaller onion, and the smaller one after that, until nothing is left.
🔑 The Key Idea in the Code
top, bottom, left, right are the four walls of the current, still-unpeeled onion layer. Every full lap (right → down → left → up) peels exactly one wall inward per side, so the "onion" strictly shrinks each pass. The two guard checks (if top <= bottom, if left <= right) exist purely so a layer that's been reduced to a single remaining row or column doesn't get walked twice — once going one direction, then again coming back.
Traversing bottom row or left column when boundaries have crossed: After traversing right and down,
topandbottomorleftandrightmay have crossed. You must verifytop <= bottombefore traversing left, andleft <= rightbefore traversing up.Allocating visited matrix when 4 boundaries suffice: Four bounding pointers (
top, bottom, left, right) achieve auxiliary space without memory allocation.Off-by-one on boundary increments: Forgetting to advance boundaries (
top += 1,right -= 1,bottom -= 1,left += 1) causes infinite loops or duplicate cell outputs.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
2D matrix spiral traversal, layer-by-layer perimeter extraction, clockwise coordinate rotation.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: Traverse along the current active boundary row or column, then shrink that boundary coordinate toward the center.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
The card's trap is the thin last ring: run the debugger on a single row such as
[[1,2,3]]to see the bottom guard skip the sweep.Off-by-one indexing on boundary corner elements (e.g. re-visiting the top-right corner during the right-column sweep).
The 60-Second Interview Pitch
Say this out loud before you type a single line
This is Spiral Matrix: I peel the matrix layer by layer with four boundaries:
top = 0,bottom = m - 1,left = 0, andright = n - 1. Whiletop <= bottomandleft <= right, I sweep right acrossmatrix[top], down alongmatrix[..][right], left acrossmatrix[bottom], and up alongmatrix[..][left], moving each boundary in right after its own sweep. Each boundary marks the first unread row or column on its side, so the unread cells always form a rectangle. The trap is the last thin ring: after the top and right sweeps there may be no row or column left, so I only sweep the bottom iftop <= bottomand the left ifleft <= right; otherwise[[1,2,3]]comes back as 1, 2, 3, 2, 1. That's O(M · N) time andO(1)extra space.
Complexity & Mathematical Proof
O(M · N)
Look at the execution steps: Maintains 4 boundary pointers (top, bottom, left, right). Traverses perimeter in clockwise order, contracting boundaries inward after each row/col. Visits each of the M · N cells exactly once.
O(1) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Output list of size M · N. Uses only 4 scalar boundary pointers in O(1) auxiliary space.
T(M, N) = M · N = O(M · N)
Derivation Progression
top → right → bottom → left
Traverses outer rectangular boundary in 4 linear segments.
top += 1, bottom -= 1, left += 1, right -= 1
Shrinks active bounding box inward after each segment in O(1).
M × N cell visits
Every element in matrix is visited and extracted exactly once.
Variable Definitions
Total number of rows in the matrix
Total number of columns in the matrix
Memory Architecture & Bounds
O(1) Iterative
O(1) 4 integer registers (output array excluded)
O(M · N) Flattened spiral array
Boundary Best / Worst Cases
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Phrasing triggers include "spiral order" and "all elements of the m x n matrix". The structural requirement is clockwise boundary-first peel: top row (left-to-right), right column (top-to-bottom), bottom row (right-to-left), and left column (bottom-to-top). The naive impulse is maintaining step vectors with a boolean visited[m][n] matrix ( auxiliary space). An experienced engineer reaches immediately for 4-Boundary Coordinate Contraction (top, bottom, left, right) running in strictly auxiliary space.
, at most cells. Time budget is strictly to visit each cell once. Auxiliary space budget is outside the output array.
The spiral cannot be produced in one pass over a matrix streamed row by row: the right-column sweep needs the last row before the walk turns back, so the whole matrix, or at least every row of the current ring, must be in memory.
Core Algorithmic State Invariants
- How Many Rings
An m x n matrix has ceil(min(m, n) / 2) rings, so the while loop runs that many times: 5 rounds for a 10 x 10 matrix, 1 round for a single row.
- Where the Spiral Ends
When min(m, n) is even, the last ring is at least two rows and two columns wide and both guards pass. When it is odd, the last ring is a single row, a single column or one cell, which is exactly the case the guards exist for.
Spiral Matrix (LeetCode 54)
You're given an m x n matrix. Read off every cell in spiral order and return that as one flat list.
Picture peeling the matrix like an onion: sweep across the still-unvisited top row heading right, then drop down the still-unvisited rightmost column, then sweep back across the still-unvisited bottom row heading left, then climb the still-unvisited leftmost column -- shrinking the unvisited region on each pass until every cell has been read.
Worked Examples
matrix = [[1,2,3],[4,5,6],[7,8,9]][1,2,3,6,9,8,7,4,5]matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]][1,2,3,4,8,12,11,10,9,5,6,7]⚖️Formal Constraints & Bounds
m == matrix.lengthn == matrix[i].length1 <= m, n <= 10-100 <= matrix[i][j] <= 100
Core Insight
Never track complex angles. Use 4 explicit boundary coordinates top, bottom, left, right. After sweeping along an outer edge, shrink that boundary inward (top += 1, right -= 1, bottom -= 1, left += 1) and guard horizontal/vertical sweeps with top <= bottom and left <= right.
Real-World Scenario & Production Applications
Printing a board, a seating chart or a label sheet in spiral order, starting from a corner and winding inward.
Step-by-Step Execution Trace Table
| Step | Direction | Active Boundary | Visited Cells | Appended to Result | Remaining Matrix Bounds |
|---|---|---|---|---|---|
| 1 | Right (→) | row = top (0) | (0,0), (0,1), (0,2) | [1, 2, 3] | top: 1, bottom: 2, left: 0, right: 2 |
| 2 | Down (↓) | col = right (2) | (1,2), (2,2) | [6, 9] | top: 1, bottom: 2, left: 0, right: 1 |
| 3 | Left (←) | row = bottom (2) | (2,1), (2,0) | [8, 7] | top: 1, bottom: 1, left: 0, right: 1 |
| 4 | Up (↑) | col = left (0) | (1,0) | [4] | top: 1, bottom: 1, left: 1, right: 1 |
| 5 | Right (→) | row = top (1) | (1,1) | [5] | top: 2, bottom: 1 (top > bottom -> Terminate) |
| 1 | top, bottom = 0, len(matrix) - 1 |
| 2 | left, right = 0, len(matrix[0]) - 1 |
| 3 | while top <= bottom and left <= right: |
| 4 | read the top row from left to right |
| 5 | top += 1 |
| 6 | read the right column from top to bottom |
| 7 | right -= 1 |
| 8 | if top <= bottom: |
| 9 | read the bottom row from right to left |
| 10 | bottom -= 1 |
| 11 | if left <= right: |
| 12 | read the left column from bottom to top |
| 13 | left += 1 |
| 14 | return result |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Four variables (top, bottom, left, right) mutating together in a loop is easy to lose track of — but they're all doing one very physical thing.
🧅 The Analogy: Peeling an Onion, Layer by Layer
Think of the matrix as an onion made of concentric rectangular rings. The outermost ring is the top row, right column, bottom row, and left column of the whole matrix. Once you've walked all the way around that ring, it's gone — you peel it off and you're left with a smaller onion (a smaller rectangle) sitting one layer inward. You repeat the exact same "walk the ring" move on the smaller onion, and the smaller one after that, until nothing is left.
🔑 The Key Idea in the Code
top, bottom, left, right are the four walls of the current, still-unpeeled onion layer. Every full lap (right → down → left → up) peels exactly one wall inward per side, so the "onion" strictly shrinks each pass. The two guard checks (if top <= bottom, if left <= right) exist purely so a layer that's been reduced to a single remaining row or column doesn't get walked twice — once going one direction, then again coming back.
Traversing bottom row or left column when boundaries have crossed: After traversing right and down,
topandbottomorleftandrightmay have crossed. You must verifytop <= bottombefore traversing left, andleft <= rightbefore traversing up.Allocating visited matrix when 4 boundaries suffice: Four bounding pointers (
top, bottom, left, right) achieve auxiliary space without memory allocation.Off-by-one on boundary increments: Forgetting to advance boundaries (
top += 1,right -= 1,bottom -= 1,left += 1) causes infinite loops or duplicate cell outputs.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
2D matrix spiral traversal, layer-by-layer perimeter extraction, clockwise coordinate rotation.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: Traverse along the current active boundary row or column, then shrink that boundary coordinate toward the center.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
The card's trap is the thin last ring: run the debugger on a single row such as
[[1,2,3]]to see the bottom guard skip the sweep.Off-by-one indexing on boundary corner elements (e.g. re-visiting the top-right corner during the right-column sweep).
The 60-Second Interview Pitch
Say this out loud before you type a single line
This is Spiral Matrix: I peel the matrix layer by layer with four boundaries:
top = 0,bottom = m - 1,left = 0, andright = n - 1. Whiletop <= bottomandleft <= right, I sweep right acrossmatrix[top], down alongmatrix[..][right], left acrossmatrix[bottom], and up alongmatrix[..][left], moving each boundary in right after its own sweep. Each boundary marks the first unread row or column on its side, so the unread cells always form a rectangle. The trap is the last thin ring: after the top and right sweeps there may be no row or column left, so I only sweep the bottom iftop <= bottomand the left ifleft <= right; otherwise[[1,2,3]]comes back as 1, 2, 3, 2, 1. That's O(M · N) time andO(1)extra space.
Complexity & Mathematical Proof
O(M · N)
Look at the execution steps: Maintains 4 boundary pointers (top, bottom, left, right). Traverses perimeter in clockwise order, contracting boundaries inward after each row/col. Visits each of the M · N cells exactly once.
O(1) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Output list of size M · N. Uses only 4 scalar boundary pointers in O(1) auxiliary space.
T(M, N) = M · N = O(M · N)
Derivation Progression
top → right → bottom → left
Traverses outer rectangular boundary in 4 linear segments.
top += 1, bottom -= 1, left += 1, right -= 1
Shrinks active bounding box inward after each segment in O(1).
M × N cell visits
Every element in matrix is visited and extracted exactly once.
Variable Definitions
Total number of rows in the matrix
Total number of columns in the matrix
Memory Architecture & Bounds
O(1) Iterative
O(1) 4 integer registers (output array excluded)
O(M · N) Flattened spiral array
Boundary Best / Worst Cases
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Phrasing triggers include "spiral order" and "all elements of the m x n matrix". The structural requirement is clockwise boundary-first peel: top row (left-to-right), right column (top-to-bottom), bottom row (right-to-left), and left column (bottom-to-top). The naive impulse is maintaining step vectors with a boolean visited[m][n] matrix ( auxiliary space). An experienced engineer reaches immediately for 4-Boundary Coordinate Contraction (top, bottom, left, right) running in strictly auxiliary space.
, at most cells. Time budget is strictly to visit each cell once. Auxiliary space budget is outside the output array.
The spiral cannot be produced in one pass over a matrix streamed row by row: the right-column sweep needs the last row before the walk turns back, so the whole matrix, or at least every row of the current ring, must be in memory.
Core Algorithmic State Invariants
- How Many Rings
An m x n matrix has ceil(min(m, n) / 2) rings, so the while loop runs that many times: 5 rounds for a 10 x 10 matrix, 1 round for a single row.
- Where the Spiral Ends
When min(m, n) is even, the last ring is at least two rows and two columns wide and both guards pass. When it is odd, the last ring is a single row, a single column or one cell, which is exactly the case the guards exist for.