4.28.2 — Spiral Matrix

LeetCode 54 · Medium

The problem

Return every element of the matrix in spiral order.

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

The matrix may be rectangular, not just square.

The pattern

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.

The two guards

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.

The solution

Python

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix:
            return []

        top, bottom = 0, len(matrix) - 1
        left, right = 0, len(matrix[0]) - 1
        result = []

        while top <= bottom and left <= right:
            for c in range(left, right + 1):          # top row, left to right
                result.append(matrix[top][c])
            top += 1

            for r in range(top, bottom + 1):          # right column, top to bottom
                result.append(matrix[r][right])
            right -= 1

            if top <= bottom:                         # 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:                         # 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

TypeScript

function spiralOrder(matrix: number[][]): number[] {
  if (!matrix.length) return [];

  let top = 0, bottom = matrix.length - 1;
  let left = 0, right = matrix[0].length - 1;
  const result: number[] = [];

  while (top <= bottom && left <= right) {
    for (let c = left; c <= right; c++) result.push(matrix[top][c]);
    top++;

    for (let r = top; r <= bottom; r++) result.push(matrix[r][right]);
    right--;

    if (top <= bottom) {
      for (let c = right; c >= left; c--) result.push(matrix[bottom][c]);
      bottom--;
    }

    if (left <= right) {
      for (let r = bottom; r >= top; r--) result.push(matrix[r][left]);
      left++;
    }
  }

  return 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.

The 1×3 case

[[1,2,3]] — this is the input that exposes a missing guard.

• top and bottom are both 0; left 0, right 2.
• Top pass emits 1, 2, 3. top becomes 1.
• Right pass: range(1, 1) is empty, so nothing. right becomes 1.
• Bottom guard: top (1) <= bottom (0) is false → skipped. Without this guard it would emit 2, 1 again.
• Left guard: left (0) <= right (1) is true, but the loop range(0, 0, -1) is empty.

Result [1,2,3] ✓. Test your solution on a single row and a single column before you say you are done.

Complexity

O(mn) time — every element is emitted once. O(1) extra space beyond the output.

The direction-vector alternative

A different formulation: keep a direction vector and turn right whenever the next cell is out of bounds or already visited.

directions = [(0,1), (1,0), (0,-1), (-1,0)]      # right, down, left, up
d = 0
r = c = 0
for _ 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.

Where this goes next

• 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.

What the interviewer will push on

"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.

Next: 4.28.3 Set Matrix Zeroes — in-place again, using the matrix itself as scratch space.