Spiral Matrix (LeetCode 54) Solution

The problem

You get an m × n matrix. Return all its elements in clockwise spiral order: along the top row left to right, down the right column, along the bottom row right to left, up the left column, then the same again on the inner ring until every element is used.

Input:
1 2 3
4 5 6
7 8 9

Output: [1, 2, 3, 6, 9, 8, 7, 4, 5]

The outer ring gives 1 2 3, 6 9, 8 7, 4, and the centre 5 comes last.

How to think about it

Start with the direct simulation. Keep four boundaries (top, bottom, left, right), walk each side of the current ring, and shrink the boundary you just finished. This is the classic answer and it is O(m·n), but it has four loops with slightly different ranges, plus checks to stop a single remaining row or column from being read twice. Most bugs in this problem are off-by-ones in those checks.

The key insight: you only ever need to read the top row. After you take the top row, look at what is left. The next thing to read is its right column, top to bottom. If you rotate the remaining matrix 90° counter-clockwise, that right column becomes the new top row, in the right order. So the whole spiral is one move repeated: take the top row, rotate the rest, repeat until the matrix is empty.

Rotation is a one-liner in Python. zip(*matrix) transposes the matrix, and reversing the list of rows after a transpose is a counter-clockwise rotation. There are no boundaries to track and no special cases for a lone row or column, because an empty matrix simply ends the loop.

Which pattern is this? Matrix simulation with index mapping. The tell is “traverse a grid in spiral / layer order”. The trade-off is that this version rebuilds the matrix every round, so it is shorter but slower than the boundary version (see Complexity).

Approach

Start with an empty result list.
While the matrix still has rows, pop the first row and append its elements to the result.
Rotate the remaining rows counter-clockwise: transpose with zip(*matrix), convert the tuples back to lists, and reverse the order of rows.
When the matrix is empty, return the result.

Solution

def spiral_order(matrix):
    res = []
    while matrix:
        res += matrix.pop(0)                                # read the top row
        matrix = [list(r) for r in zip(*matrix)][::-1]      # rotate rest counter-clockwise
    return res
# spiral_order([[1,2,3],[4,5,6],[7,8,9]]) -> [1,2,3,6,9,8,7,4,5]

Dry run

On the 3 × 3 example:

Round	Top row taken	`res` after	Matrix left (after rotation)
1	`[1, 2, 3]`	`[1,2,3]`	`[[6,9],[5,8],[4,7]]`
2	`[6, 9]`	`[1,2,3,6,9]`	`[[8,7],[5,4]]`
3	`[8, 7]`	`[1,2,3,6,9,8,7]`	`[[4],[5]]`
4	`[4]`	`[1,2,3,6,9,8,7,4]`	`[[5]]`
5	`[5]`	`[1,2,3,6,9,8,7,4,5]`	`[]`

Each rotation brings the next side of the spiral to the top. The answer is [1, 2, 3, 6, 9, 8, 7, 4, 5].

Complexity

Time: O(m·n·min(m, n)) for this version. Every round rebuilds the whole remaining matrix, and it takes about four rounds to peel each ring, with min(m, n)/2 rings. For a square n × n matrix that is O(n³). The four-boundary version visits each cell once and is O(m·n); mention it if the interviewer asks for the optimal bound.
Space: O(m·n). Each rotation builds a new copy of the remaining matrix (the output list is O(m·n) too).

Edge cases and pitfalls

Empty matrix [] returns []: the while loop never runs.
Single row or single column works with no special case, which is where the boundary version usually breaks.
The input is destroyed. pop(0) and the rebinding consume the matrix; pass a copy if the caller still needs it.
Rotating the wrong way. A clockwise rotation would bring the left column to the top and read the spiral backwards. Transpose then reverse the row list is counter-clockwise.
Claiming O(m·n) for this version is a common slip; know why the rebuilds cost more.

Rotate Image (LeetCode 48): the same transpose-plus-reverse rotation, done in place.
Set Matrix Zeroes (LeetCode 73): another matrix problem decided by careful row and column bookkeeping.
Game of Life (LeetCode 289): grid simulation where the order of updates matters.