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.

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.

Brute Force Approach

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.

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;
}

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.

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.

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

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.