Spiral Matrix

Spiral Matrix has no trick, only bookkeeping. That is exactly why it is asked: it tests whether you can keep four indices straight under pressure and whether you test the shapes that break them. Nearly every wrong answer passes on a square matrix and fails on a single row.

The problem

Given an m × n matrix, return all its values in spiral order: start at the top-left, go right along the top row, down the right column, left along the bottom row, up the left column, and continue inward.

Example 1.

 1  2  3  4 5  6  7  8 9 10 11 12

→ [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7].

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

Constraints. 1 ≤ m, n ≤ 10.

Clarifying questions

• Can the matrix be non-square? Yes — Example 1 is 3 × 4. This is the whole difficulty.
• Can it be a single row or column? Yes.
• Can it be empty? Not under these constraints, but return [] if it is.
• Clockwise, starting top-left? Yes.

Approach 1: the simple way — walk and turn

Simulate a walker. Keep a direction (right, down, left, up) and a seen grid. Step forward; if the next cell is outside the matrix or already seen, turn right.

1def spiral_visited(matrix: list[list[int]]) -> list[int]:2    """Simulate: walk forward, turn clockwise at a wall or a visited cell."""3    if not matrix or not matrix[0]:4        return []5    rows, cols = len(matrix), len(matrix[0])6    seen = [[False] * cols for _ in range(rows)]7    dr, dc = [0, 1, 0, -1], [1, 0, -1, 0]      # right, down, left, up8    r = c = d = 09    result = []10    for _ in range(rows * cols):11        result.append(matrix[r][c])12        seen[r][c] = True13        nr, nc = r + dr[d], c + dc[d]14        if not (0 <= nr < rows and 0 <= nc < cols) or seen[nr][nc]:15            d = (d + 1) % 4                      # turn right16            nr, nc = r + dr[d], c + dc[d]17        r, c = nr, nc18    return result

It is correct and O(m × n) time — every cell is visited once. The cost is the seen grid: O(m × n) extra space. The interviewer will ask for O(1) extra space, and the seen grid exists only to tell us where the "walls" are.

The key insight

The visited cells always form complete outer rings. So instead of remembering every visited cell, remember only where the unvisited rectangle is: its top row, bottom row, left column and right column. Four numbers replace the whole seen grid.

Each pass along an edge consumes that edge, so the matching boundary moves inward by one. After the top row is read, top goes down. After the right column, right goes left. And so on, until the rectangle is empty.

There is one catch. On a rectangle that is wider than it is tall, the rows run out before the columns do. After the top row is consumed, the "bottom row" may be the same row, already read. So before reading the bottom row, check that a row is still left (top <= bottom), and before reading the left column, check that a column is still left (left <= right).

Approach 2: four shrinking boundaries

1def spiral_order(matrix: list[list[int]]) -> list[int]:2    """Read the outer ring, shrink the four boundaries, repeat."""3    if not matrix or not matrix[0]:4        return []5    top, bottom = 0, len(matrix) - 16    left, right = 0, len(matrix[0]) - 17    result: list[int] = []8    while top <= bottom and left <= right:9        for c in range(left, right + 1):            # top row, left to right10            result.append(matrix[top][c])11        top += 112        for r in range(top, bottom + 1):            # right column, top to bottom13            result.append(matrix[r][right])14        right -= 115        if top <= bottom:                           # a row is still left16            for c in range(right, left - 1, -1):    # bottom row, right to left17                result.append(matrix[bottom][c])18            bottom -= 119        if left <= right:                           # a column is still left20            for r in range(bottom, top - 1, -1):    # left column, bottom to top21                result.append(matrix[r][left])22            left += 123    return result

Step by step:

1. The boundaries are inclusive: top is the first unread row, bottom the last unread row, and the same for columns.
2. Read each edge, then move its boundary inward.
3. Guard the bottom and left passes, which are the ones that can repeat a row or column already read.

Dry run on Example 1 (3 × 4). Boundaries are shown when each pass starts.

The loop ends because top > bottom. The result is [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7], and it has 12 values — exactly 3 × 4.

Complexity. O(m × n) time: each cell is appended once, and each pass does work only for the cells it reads. O(1) extra space besides the output.

The boundary version matched the simulation on 300 random matrices of every shape from 1 × 1 to 7 × 7.

Edge cases

• A single row [[1, 2, 3]]. The top pass reads everything and top becomes 1, past bottom = 0. The guard skips the bottom pass. Without guards, the output is [1, 2, 3, 2, 1].
• A single column [[1], [2], [3]]. The right-column pass reads 2 and 3; right becomes −1. The guard skips the left pass. Without guards, the output is [1, 2, 3, 2].
• 1 × 1. The top pass reads the one value, and every other pass is empty or skipped.
• Odd square (3 × 3). The centre is read as a one-cell top row in the last round.

Follow-ups

• "Generate an n × n matrix filled with 1 to n² in spiral order." Same four boundaries, but write a counter into each cell instead of reading. For a square matrix the guards never change the output, but keeping them costs nothing.
• "Spiral order anticlockwise." Change the pass order: left column down, bottom row right, right column up, top row left.
• "Start from a given cell and spiral outwards." Now there are no walls to shrink. Walk with step lengths 1, 1, 2, 2, 3, 3 … and keep only the cells that fall inside the grid.