Builds on Converging Pointers, which you haven’t finished yet.
Spiral Matrix Traversal (Layer-by-Layer Boundary Shrinking)
Spiral Matrix (LC 54)(opens leetcode.com)
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.
Spiral Matrix
grid (R x C) ➔ top/bottom/left/right ➔ inward spiral| 1 | def spiral_order(matrix: list[list[int]]) -> list[int]: |
| 2 | """Spiral Matrix: read the matrix ring by ring with four boundaries. |
| 3 | Time: O(R * C) | Space: O(1) auxiliary |
| 4 | """ |
| 5 | if not matrix or not matrix[0]: |
| 6 | return [] |
| 7 | |
| 8 | top, bottom = 0, len(matrix) - 1 |
| 9 | left, right = 0, len(matrix[0]) - 1 |
| 10 | result: list[int] = [] |
| 11 | |
| 12 | while top <= bottom and left <= right: |
| 13 | # 1. Sweep Top (Left -> Right) |
| 14 | for c in range(left, right + 1): |
| 15 | result.append(matrix[top][c]) |
| 16 | top += 1 |
| 17 | |
| 18 | # 2. Sweep Right (Top -> Bottom) |
| 19 | for r in range(top, bottom + 1): |
| 20 | result.append(matrix[r][right]) |
| 21 | right -= 1 |
| 22 | |
| 23 | # 3. Sweep Bottom (Right -> Left) with Guard! |
| 24 | if top <= bottom: |
| 25 | for c in range(right, left - 1, -1): |
| 26 | result.append(matrix[bottom][c]) |
| 27 | bottom -= 1 |
| 28 | |
| 29 | # 4. Sweep Left (Bottom -> Top) with Guard! |
| 30 | if left <= right: |
| 31 | for r in range(bottom, top - 1, -1): |
| 32 | result.append(matrix[r][left]) |
| 33 | left += 1 |
| 34 | |
| 35 | return result |
top, bottom, left and right always bound exactly the cells not yet added to result.Walk the matrix one ring at a time with four boundaries, top, bottom, left and right, that close in from all four sides like converging pointers, and move each boundary inward right after its side is read. Each boundary marks the first row or column not yet read on its side, so after the four sweeps the unread cells form a smaller rectangle and the same sweeps repeat on it. The trap is the last, thin ring: after the top and right sweeps there may be no row or no column left, so guard the bottom sweep with if top <= bottom and the left sweep with if left <= right, or a single row such as [[1,2,3]] returns [1,2,3,2,1].
See it run
Spiral Matrix: peeling a 3 x 4 matrix with four boundaries
top 0bottom 2left 0right 3result []
Each cell shows its value until it is read. A blank cell is already in result.
reada cell this sweep adds to resultagaina cell the skipped sweep would add a second time
The matrix has 3 rows and 4 columns, so top = 0, bottom = 2, left = 0 and right = 3. A cell that is read becomes blank.
Gotcha 1 of 4
- The trap
Gotcha 1: Leaving out the
if top <= bottomguardMistakefor c in range(right, left - 1, -1): result.append(matrix[bottom][c]) bottom -= 1Fixif top <= bottom: for c in range(right, left - 1, -1): result.append(matrix[bottom][c]) bottom -= 1What happens: After the top sweep and the right sweep, the rows may be used up. For
[[1,2,3]], the top sweep reads row 0 and setstopto 1, whilebottomis 0. Without the guard, the bottom sweep reads row 0 again, backwards. The left sweep needsif left <= rightfor the same reason.Example: matrix = [[1, 2, 3]]Mistake: returns [1, 2, 3, 2, 1]Fix: returns [1, 2, 3]
- The grid is read in plain row order and every value moves forward by the same number of places, as in Shift 2D Grid (LC 1260), not ring by ring. See Three-Reversals Algorithm
Deep Dive
What the four boundaries mean
top, bottom, left and right mark the rectangle of cells that are not in result yet. Cell matrix[r][c] is unread exactly when top <= r <= bottom and left <= c <= right. This is the card's invariant.
Each sweep reads one side of that rectangle, and then moves the boundary on that side inward by 1. The side that was just read is no longer inside the rectangle. So the rectangle always shrinks by exactly the cells that were read.
In Spiral Matrix (LC 54) with a 3 by 4 matrix, the first four sweeps read 1, 2, 3, 4, then 8, 12, then 11, 10, 9, then 5. The rectangle is now one row and two columns: top = 1, bottom = 1, left = 1, right = 2. The second ring reads 6, 7. The final result is [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7].
Why each cell is read exactly once
The four sweeps of one ring read the top row, the right column, the bottom row and the left column of the rectangle. The top row is read first, and top += 1 removes it from the rectangle. So the right sweep starts at top, which is the row below the top-right corner. That corner is not read twice.
The same order removes the other corners. right -= 1 removes the right column before the bottom sweep, so the bottom sweep starts at the cell left of the bottom-right corner. bottom -= 1 removes the bottom row before the left sweep, so the left sweep stops above the bottom-left corner.
Every cell is in one ring, and every ring is read by one pass of the while loop. So result gets R * C values, one per cell, and no cell appears twice. The number of rings is the smaller side divided by 2, rounded up. A 3 by 4 matrix has 2 rings, a 5 by 5 matrix has 3 rings, and a matrix with one row has 1 ring.
Why the last ring needs two guards
A full ring has at least two rows and two columns. The last ring can be one row, one column or one cell. In that case the top sweep and the right sweep can already use up the rows or the columns.
The 3 by 4 example shows this. In the second ring, the top sweep reads 6, 7 and sets top = 2, while bottom = 1. The test top <= bottom is false, so the bottom sweep is skipped. Without the guard, it runs range(right, left - 1, -1) on row 1 and adds 6 a second time. The result then ends with ..., 5, 6, 7, 6.
The single row [[1, 2, 3]] gives [1, 2, 3, 2, 1] without the first guard. The single column [[1], [2], [3]] gives [1, 2, 3, 2] without the second guard, left <= right. With both guards, the results are [1, 2, 3] for both inputs.
The rule is: after a sweep changes a boundary, ask whether the next side still has cells. The top sweep and the right sweep do not need a guard, because the while condition already guarantees one row and one column at the start of each ring.
The cost, and the same boundaries in related problems
Every cell is read once, so the time is O(R * C). The only extra memory is four integers, so the auxiliary space is O(1). The output list holds R * C values, but it is the answer and does not count as extra memory.
A different method keeps a visited grid and a direction, and turns right when the next cell is outside the matrix or already visited. It produces the same order, but it needs O(R * C) extra memory for visited.
The same four boundaries solve Spiral Matrix II (LC 59), which writes the numbers 1 to n * n into an empty grid in spiral order: replace result.append(...) with an assignment from a counter. Spiral Matrix IV (LC 2326) does the same with the values of a linked list. Rotate Image (LC 48) and Cyclically Rotating a Grid (LC 1914) treat each ring as a closed loop of cells, and move the values along that loop.
60-Second Pitch
"I read the matrix ring by ring with four boundaries: top, bottom, left and right. They enclose exactly the cells that are not in the result yet. Each pass reads the top row, the right column, the bottom row and the left column. After each sweep, I move the boundary on that side inward by 1. The last ring can be one row or one column. So I check top <= bottom before the bottom sweep and left <= right before the left sweep. Without them, a cell would be read twice. Every cell is read once, so the time is O(R * C). I keep four integers, so the extra space is O(1)."
Common Questions
- Why are only the bottom sweep and the left sweep guarded?
The
whilecondition guarantees at least one row and one column at the start of the pass. So the top sweep and the right sweep always have cells to read. The top sweep then removes a row and the right sweep removes a column. After that, the rectangle can be empty in one direction, so the bottom sweep and the left sweep each need a check.- What is the time and space complexity of
spiral_order? O(R * C) time, because every cell is added to
resultonce and the boundary updates are constant work. The auxiliary space isO(1): four integers. The output list holds R * C values, and it is the answer.- How does a
visitedgrid compare with the boundary method? The
visitedmethod walks one cell at a time in a direction and turns when the next cell is outside the matrix or already visited. It gives the same order and the same O(R * C) time. It needs an extra grid of R * C flags. The boundary method needs no extra grid.- How do you change the code to fill a grid, as in Spiral Matrix II (LC 59)?
Create an n by n grid of zeros. Use the same four boundaries and the same four sweeps. Replace each
result.append(matrix[r][c])withgrid[r][c] = counter, and then add 1 tocounter. The guards stay, although for a square grid the only thin ring is the center cell of an odd n.- What changes for Rotate Image (LC 48)?
The task does not read the cells in order. It turns each ring by a quarter. For each
iinrange(right - left), four cells swap positions through one saved value. A side hasright - left + 1cells, but its last cell starts the next side, so the loop runsright - lefttimes.
SWE Reasoning
Spot it
- The output order or the update order is a spiral: inward, ring by ring, starting at a corner.
- The task writes values into a grid in spiral order, as in Spiral Matrix II (LC 59), or reads them in spiral order, as in Spiral Matrix (LC 54).
- The task moves each ring of a grid as a loop, as in Rotate Image (LC 48) or Cyclically Rotating a Grid (LC 1914).
- The matrix may have one row, one column or one cell left in the middle, and the code must not read it twice.
- You are asked for
O(1)extra memory, so avisitedgrid is not allowed.
The invariant, step by step
- At the start of a loop pass,
top,bottom,leftandrightenclose exactly the cells not inresult. Thewhilecondition says this rectangle has at least one row and one column. - The top sweep reads row
topfromlefttoright. Thentop += 1removes that row from the rectangle. - The right sweep reads column
rightfrom the newtoptobottom. Thenright -= 1removes that column. - Before the bottom sweep,
if top <= bottomasks whether a row is left. If it is, the sweep reads rowbottomfromrighttoleft, andbottom -= 1removes it. - Before the left sweep,
if left <= rightasks whether a column is left. If it is, the sweep reads columnleftfrombottomtotop, andleft += 1removes it. - The four boundaries again enclose exactly the unread cells, so the invariant holds for the next pass. The loop ends when the rectangle has no cell, and
resulthas every cell once.
Traps
- No
top <= bottomguard. On a thin last ring, the bottom sweep reads a row that was already read. For[[1, 2, 3]], the result is[1, 2, 3, 2, 1]. - No
left <= rightguard. On a single column, the left sweep reads a column that was already read. For[[1], [2], [3]]without this guard, the result is[1, 2, 3, 2]. - A boundary is not moved after its sweep. The next sweep then starts on a cell that is already in
result, so the corner is read twice. - A
rangethat stops one cell early.range(right, left, -1)stops before columnleft, so the bottom sweep skips the bottom-left corner. Userange(right, left - 1, -1). - An empty matrix.
matrix[0]raisesIndexErrorfor[]. The first line,if not matrix or not matrix[0], returns[]instead.
Practice
Builds on Converging Pointers, which you haven’t finished yet.
Spiral Matrix Traversal (Layer-by-Layer Boundary Shrinking)
Spiral Matrix (LC 54)(opens leetcode.com)
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.
Spiral Matrix
grid (R x C) ➔ top/bottom/left/right ➔ inward spiral| 1 | def spiral_order(matrix: list[list[int]]) -> list[int]: |
| 2 | """Spiral Matrix: read the matrix ring by ring with four boundaries. |
| 3 | Time: O(R * C) | Space: O(1) auxiliary |
| 4 | """ |
| 5 | if not matrix or not matrix[0]: |
| 6 | return [] |
| 7 | |
| 8 | top, bottom = 0, len(matrix) - 1 |
| 9 | left, right = 0, len(matrix[0]) - 1 |
| 10 | result: list[int] = [] |
| 11 | |
| 12 | while top <= bottom and left <= right: |
| 13 | # 1. Sweep Top (Left -> Right) |
| 14 | for c in range(left, right + 1): |
| 15 | result.append(matrix[top][c]) |
| 16 | top += 1 |
| 17 | |
| 18 | # 2. Sweep Right (Top -> Bottom) |
| 19 | for r in range(top, bottom + 1): |
| 20 | result.append(matrix[r][right]) |
| 21 | right -= 1 |
| 22 | |
| 23 | # 3. Sweep Bottom (Right -> Left) with Guard! |
| 24 | if top <= bottom: |
| 25 | for c in range(right, left - 1, -1): |
| 26 | result.append(matrix[bottom][c]) |
| 27 | bottom -= 1 |
| 28 | |
| 29 | # 4. Sweep Left (Bottom -> Top) with Guard! |
| 30 | if left <= right: |
| 31 | for r in range(bottom, top - 1, -1): |
| 32 | result.append(matrix[r][left]) |
| 33 | left += 1 |
| 34 | |
| 35 | return result |
top, bottom, left and right always bound exactly the cells not yet added to result.Walk the matrix one ring at a time with four boundaries, top, bottom, left and right, that close in from all four sides like converging pointers, and move each boundary inward right after its side is read. Each boundary marks the first row or column not yet read on its side, so after the four sweeps the unread cells form a smaller rectangle and the same sweeps repeat on it. The trap is the last, thin ring: after the top and right sweeps there may be no row or no column left, so guard the bottom sweep with if top <= bottom and the left sweep with if left <= right, or a single row such as [[1,2,3]] returns [1,2,3,2,1].
See it run
Spiral Matrix: peeling a 3 x 4 matrix with four boundaries
top 0bottom 2left 0right 3result []
Each cell shows its value until it is read. A blank cell is already in result.
reada cell this sweep adds to resultagaina cell the skipped sweep would add a second time
The matrix has 3 rows and 4 columns, so top = 0, bottom = 2, left = 0 and right = 3. A cell that is read becomes blank.
Gotcha 1 of 4
- The trap
Gotcha 1: Leaving out the
if top <= bottomguardMistakefor c in range(right, left - 1, -1): result.append(matrix[bottom][c]) bottom -= 1Fixif top <= bottom: for c in range(right, left - 1, -1): result.append(matrix[bottom][c]) bottom -= 1What happens: After the top sweep and the right sweep, the rows may be used up. For
[[1,2,3]], the top sweep reads row 0 and setstopto 1, whilebottomis 0. Without the guard, the bottom sweep reads row 0 again, backwards. The left sweep needsif left <= rightfor the same reason.Example: matrix = [[1, 2, 3]]Mistake: returns [1, 2, 3, 2, 1]Fix: returns [1, 2, 3]
- The grid is read in plain row order and every value moves forward by the same number of places, as in Shift 2D Grid (LC 1260), not ring by ring. See Three-Reversals Algorithm
Deep Dive
What the four boundaries mean
top, bottom, left and right mark the rectangle of cells that are not in result yet. Cell matrix[r][c] is unread exactly when top <= r <= bottom and left <= c <= right. This is the card's invariant.
Each sweep reads one side of that rectangle, and then moves the boundary on that side inward by 1. The side that was just read is no longer inside the rectangle. So the rectangle always shrinks by exactly the cells that were read.
In Spiral Matrix (LC 54) with a 3 by 4 matrix, the first four sweeps read 1, 2, 3, 4, then 8, 12, then 11, 10, 9, then 5. The rectangle is now one row and two columns: top = 1, bottom = 1, left = 1, right = 2. The second ring reads 6, 7. The final result is [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7].
Why each cell is read exactly once
The four sweeps of one ring read the top row, the right column, the bottom row and the left column of the rectangle. The top row is read first, and top += 1 removes it from the rectangle. So the right sweep starts at top, which is the row below the top-right corner. That corner is not read twice.
The same order removes the other corners. right -= 1 removes the right column before the bottom sweep, so the bottom sweep starts at the cell left of the bottom-right corner. bottom -= 1 removes the bottom row before the left sweep, so the left sweep stops above the bottom-left corner.
Every cell is in one ring, and every ring is read by one pass of the while loop. So result gets R * C values, one per cell, and no cell appears twice. The number of rings is the smaller side divided by 2, rounded up. A 3 by 4 matrix has 2 rings, a 5 by 5 matrix has 3 rings, and a matrix with one row has 1 ring.
Why the last ring needs two guards
A full ring has at least two rows and two columns. The last ring can be one row, one column or one cell. In that case the top sweep and the right sweep can already use up the rows or the columns.
The 3 by 4 example shows this. In the second ring, the top sweep reads 6, 7 and sets top = 2, while bottom = 1. The test top <= bottom is false, so the bottom sweep is skipped. Without the guard, it runs range(right, left - 1, -1) on row 1 and adds 6 a second time. The result then ends with ..., 5, 6, 7, 6.
The single row [[1, 2, 3]] gives [1, 2, 3, 2, 1] without the first guard. The single column [[1], [2], [3]] gives [1, 2, 3, 2] without the second guard, left <= right. With both guards, the results are [1, 2, 3] for both inputs.
The rule is: after a sweep changes a boundary, ask whether the next side still has cells. The top sweep and the right sweep do not need a guard, because the while condition already guarantees one row and one column at the start of each ring.
The cost, and the same boundaries in related problems
Every cell is read once, so the time is O(R * C). The only extra memory is four integers, so the auxiliary space is O(1). The output list holds R * C values, but it is the answer and does not count as extra memory.
A different method keeps a visited grid and a direction, and turns right when the next cell is outside the matrix or already visited. It produces the same order, but it needs O(R * C) extra memory for visited.
The same four boundaries solve Spiral Matrix II (LC 59), which writes the numbers 1 to n * n into an empty grid in spiral order: replace result.append(...) with an assignment from a counter. Spiral Matrix IV (LC 2326) does the same with the values of a linked list. Rotate Image (LC 48) and Cyclically Rotating a Grid (LC 1914) treat each ring as a closed loop of cells, and move the values along that loop.
60-Second Pitch
"I read the matrix ring by ring with four boundaries: top, bottom, left and right. They enclose exactly the cells that are not in the result yet. Each pass reads the top row, the right column, the bottom row and the left column. After each sweep, I move the boundary on that side inward by 1. The last ring can be one row or one column. So I check top <= bottom before the bottom sweep and left <= right before the left sweep. Without them, a cell would be read twice. Every cell is read once, so the time is O(R * C). I keep four integers, so the extra space is O(1)."
Common Questions
- Why are only the bottom sweep and the left sweep guarded?
The
whilecondition guarantees at least one row and one column at the start of the pass. So the top sweep and the right sweep always have cells to read. The top sweep then removes a row and the right sweep removes a column. After that, the rectangle can be empty in one direction, so the bottom sweep and the left sweep each need a check.- What is the time and space complexity of
spiral_order? O(R * C) time, because every cell is added to
resultonce and the boundary updates are constant work. The auxiliary space isO(1): four integers. The output list holds R * C values, and it is the answer.- How does a
visitedgrid compare with the boundary method? The
visitedmethod walks one cell at a time in a direction and turns when the next cell is outside the matrix or already visited. It gives the same order and the same O(R * C) time. It needs an extra grid of R * C flags. The boundary method needs no extra grid.- How do you change the code to fill a grid, as in Spiral Matrix II (LC 59)?
Create an n by n grid of zeros. Use the same four boundaries and the same four sweeps. Replace each
result.append(matrix[r][c])withgrid[r][c] = counter, and then add 1 tocounter. The guards stay, although for a square grid the only thin ring is the center cell of an odd n.- What changes for Rotate Image (LC 48)?
The task does not read the cells in order. It turns each ring by a quarter. For each
iinrange(right - left), four cells swap positions through one saved value. A side hasright - left + 1cells, but its last cell starts the next side, so the loop runsright - lefttimes.
SWE Reasoning
Spot it
- The output order or the update order is a spiral: inward, ring by ring, starting at a corner.
- The task writes values into a grid in spiral order, as in Spiral Matrix II (LC 59), or reads them in spiral order, as in Spiral Matrix (LC 54).
- The task moves each ring of a grid as a loop, as in Rotate Image (LC 48) or Cyclically Rotating a Grid (LC 1914).
- The matrix may have one row, one column or one cell left in the middle, and the code must not read it twice.
- You are asked for
O(1)extra memory, so avisitedgrid is not allowed.
The invariant, step by step
- At the start of a loop pass,
top,bottom,leftandrightenclose exactly the cells not inresult. Thewhilecondition says this rectangle has at least one row and one column. - The top sweep reads row
topfromlefttoright. Thentop += 1removes that row from the rectangle. - The right sweep reads column
rightfrom the newtoptobottom. Thenright -= 1removes that column. - Before the bottom sweep,
if top <= bottomasks whether a row is left. If it is, the sweep reads rowbottomfromrighttoleft, andbottom -= 1removes it. - Before the left sweep,
if left <= rightasks whether a column is left. If it is, the sweep reads columnleftfrombottomtotop, andleft += 1removes it. - The four boundaries again enclose exactly the unread cells, so the invariant holds for the next pass. The loop ends when the rectangle has no cell, and
resulthas every cell once.
Traps
- No
top <= bottomguard. On a thin last ring, the bottom sweep reads a row that was already read. For[[1, 2, 3]], the result is[1, 2, 3, 2, 1]. - No
left <= rightguard. On a single column, the left sweep reads a column that was already read. For[[1], [2], [3]]without this guard, the result is[1, 2, 3, 2]. - A boundary is not moved after its sweep. The next sweep then starts on a cell that is already in
result, so the corner is read twice. - A
rangethat stops one cell early.range(right, left, -1)stops before columnleft, so the bottom sweep skips the bottom-left corner. Userange(right, left - 1, -1). - An empty matrix.
matrix[0]raisesIndexErrorfor[]. The first line,if not matrix or not matrix[0], returns[]instead.