Return every element of the matrix in spiral order.
1 2 34 5 6 → [1,2,3,6,9,8,7,4,5]7 8 9
The matrix may be rectangular, not just square.
Restating the Problem: You are given a 2D matrix (rows and columns). Imagine you are walking through the matrix starting from the top-left, going right. When you hit an edge or a cell you've already visited, you turn right. You continue spiraling inward until you've visited every single cell. You need to return the elements in the order you visited them.
Constraints to note: The matrix dimensions m and n are up to 10. Again, small inputs, but the challenge is purely implementation.
Edge cases: A matrix with a single row ([1, 2, 3]), or a single column.
There isn't a traditional "brute force vs optimized" trade-off here because the task requires visiting every cell exactly once, which inherently takes O(m \times n) time. Any correct simulation is essentially optimal in time complexity. However, a naive simulation might use a visited matrix of size m \times n (taking extra space) and turn right whenever it hits an edge or a visited cell. The boundary-shrinking method is much more space-efficient.
Track four boundaries — top, bottom, left, right — and peel one edge at a time, shrinking the boundary you just consumed.
→ → → walk the TOP row, then top++↑ ↓ walk the RIGHT col, then right--↑ ↓ walk the BOTTOM row, then bottom--← ← ← walk the LEFT col, then left++
Repeat until the boundaries cross.
The difficulty is entirely in the boundary checks, not the idea. On a matrix with one row left, the bottom pass would walk the same row again backwards; on one column left, the left pass would repeat it. Both need guarding.
After the top row and the right column are consumed, check before doing the other two:
Before the bottom row: only if top <= bottom. A single remaining row was already taken by the top pass.
Before the left column: only if left <= right. A single remaining column was already taken by the right pass.
Miss these and elements are emitted twice — and it only shows up on rectangular matrices or at the very centre, which is why this problem catches people who tested on a 3×3.
class Solution: def spiralOrder(self, matrix: List[List[int]]) -> List[int]: if not matrix: # (1) return [] top, bottom = 0, len(matrix) - 1 # (2) left, right = 0, len(matrix[0]) - 1 # (3) result = [] while top <= bottom and left <= right: # (4) for c in range(left, right + 1): # (5) top row, left to right result.append(matrix[top][c]) top += 1 # (6) for r in range(top, bottom + 1): # (7) right column, top to bottom result.append(matrix[r][right]) right -= 1 # (8) if top <= bottom: # (9) guard: rows remain for c in range(right, left - 1, -1): # bottom row, right to left result.append(matrix[bottom][c]) bottom -= 1 if left <= right: # (10) guard: columns remain for r in range(bottom, top - 1, -1): # left column, bottom to top result.append(matrix[r][left]) left += 1 return result
ts
function spiralOrder(matrix: number[][]): number[] { if (!matrix.length) return []; // (1) let top = 0, bottom = matrix.length - 1; // (2) let left = 0, right = matrix[0].length - 1; // (3) const result: number[] = []; while (top <= bottom && left <= right) { // (4) for (let c = left; c <= right; c++) result.push(matrix[top][c]); // (5) top++; // (6) for (let r = top; r <= bottom; r++) result.push(matrix[r][right]); // (7) right--; // (8) if (top <= bottom) { // (9) for (let c = right; c >= left; c--) result.push(matrix[bottom][c]); bottom--; } if (left <= right) { // (10) for (let r = bottom; r >= top; r--) result.push(matrix[r][left]); left++; } } return result;}
Keep four walls: the top row, bottom row, left column and right column that have not been read yet. Each lap reads the outer ring and moves every wall inward by one.
(1) An empty grid gives an empty list.
(2) The top and bottom unread rows.
(3) The left and right unread columns.
(4) Keep going while there is at least one unread cell, meaning the walls have not crossed.
(5) Read the top row, left to right, then
(6) move the top wall down. That row is done.
(7) Read the right column, top to bottom, then
(8) move the right wall left.
(9) Read the bottom row, right to left, only if a row is still left. In a grid with one row, step (5) already read it. Without this check, it would be read again backwards.
(10) Read the left column, bottom to top, only if a column is still left. Same reason, for a grid with one column.
Code Walkthrough:
Initialization: We establish four boundaries: top, bottom, left, and right, representing the unvisited core of the matrix. We also initialize a result array.
Loop Condition (top <= bottom and left <= right): We continue peeling layers as long as there is an unvisited core.
Peeling the Top: We loop from left to right along the top row. Once done, we increment top because that row is consumed.
Peeling the Right: We loop from top to bottom along the right column. Once done, we decrement right.
Peeling the Bottom (with Guard): If top <= bottom (meaning we still have rows left), we loop from right down to left along the bottom row, then decrement bottom.
Peeling the Left (with Guard): If left <= right (meaning columns remain), we loop from bottom up to top along the left column, then increment left.
Return: We return the result.
The boundary is shrunk immediately after each pass, so the next pass starts from the correct place. Doing all four passes and then adjusting all four boundaries produces overlaps.
The top and right passes need no guard, because the outer while has just confirmed both boundaries are valid.
The bottom and left passes do, because top++ and right-- may have crossed the boundaries in the meantime.
O(mn) time — every element is emitted once. O(1) extra space beyond the output.
Time Complexity:O(mn). We touch every element in the m \times n matrix exactly once.
Space Complexity:O(1). We only use four integer pointers (top, bottom, left, right) and loop variables. The result array is required for the output, so it's not counted as extra auxiliary space.
A different formulation: keep a direction vector and turn right whenever the next cell is out of bounds or already visited.
python
directions = [(0,1), (1,0), (0,-1), (-1,0)] # right, down, left, upd = 0r = c = 0for _ in range(rows * cols): result.append(matrix[r][c]) matrix[r][c] = None # mark visited nr, nc = r + directions[d][0], c + directions[d][1] if not (0 <= nr < rows and 0 <= nc < cols) or matrix[nr][nc] is None: d = (d + 1) % 4 # turn right nr, nc = r + directions[d][0], c + directions[d][1] r, c = nr, nc
(d + 1) % 4 cycling through four direction vectors is a genuinely useful idiom — it appears in robot-simulation problems and grid walks throughout this book.
It needs to mark visited cells, which either mutates the input or costs O(mn) space. The boundary version is cleaner here, but the direction-vector idea is the one that transfers.
Spiral Matrix II — fill an n × n matrix with 1 to n² in spiral order. Same loop, writing instead of reading.
Spiral Matrix III — spiral outwards from a point, possibly leaving the grid. The direction-vector form is the natural fit, with the step length growing 1, 1, 2, 2, 3, 3, …
Rotate Image — a different traversal of the same grid. 4.28.1.
"Where are the guards and why?" Before the bottom and left passes, because a single remaining row or column has already been consumed.
"Test it on a 1×n matrix." Do this unprompted; it is the case the problem is designed around.
"Why shrink the boundary immediately?" So the next pass starts in the right place.
"What if the matrix is empty?" The early return, and note that matrix[0] would throw without it.
"Is there another formulation?" Direction vectors with (d + 1) % 4, at the cost of marking visited cells.
One thing to volunteer: walk the 1×3 case out loud before writing code. It shows you know where the bug lives rather than discovering it from a failing test.