Spiral Matrix Traversal: The Four-Boundary Method

"Return all elements of the matrix in spiral order." The problem has no clever algorithm hiding in it — every cell is read once, in an order you can draw with a finger. What makes it hard is the bookkeeping: off-by-one errors at the corners and a middle row that gets read twice. The four-boundary method removes most of that bookkeeping by keeping one simple fact true for the whole loop.

The problem it solves

Given a grid with rows rows and cols columns, output its values clockwise from the top-left corner: along the top row, down the right column, back along the bottom row, up the left column, then the same again one ring further in. The grid need not be square, and it may be a single row or a single column.

The same traversal appears in variations — filling a matrix with 1 to n² in spiral order, printing a matrix anticlockwise, or walking outward from the centre — so a version you can reason about pays off more than once.

The intuition

Do not track a direction and a turn counter. Track the unread rectangle instead. Four numbers describe it: top, bottom, left and right, the first and last row and column that still hold unread cells.

One lap is four moves, and each move reads a whole edge of that rectangle and then shrinks it:

• Read the top row from left to right, then move top down by one.
• Read the right column from top to bottom, then move right in by one.
• Read the bottom row from right back to left, then move bottom up by one.
• Read the left column from bottom back up to top, then move left in by one.

The invariant is that the rectangle always contains exactly the cells not yet read. When top passes bottom or left passes right, the rectangle is empty and the loop stops.

There is one catch. After the first two moves, the rectangle may already be empty — a grid of one row has nothing left once its top row is read. The third and fourth moves each need a check that a row or column is still there. Without them, the bottom move reads the same single row again, backwards.

Watch it run

The animation reads a 4 × 4 board. The dashed rectangle is the four walls. Each step walks one edge and pulls that wall in, until the walls cross over the last cell. The readout counts cells output so far, which ends at sixteen — each cell once.

The code

The four moves, with the two guards, and the same loop without them:

def spiral(grid):
    if not grid or not grid[0]:
        return []
    top, bottom = 0, len(grid) - 1
    left, right = 0, len(grid[0]) - 1
    out = []
    while top <= bottom and left <= right:
        for c in range(left, right + 1):          # top wall, left to right
            out.append(grid[top][c])
        top += 1
        for r in range(top, bottom + 1):          # right wall, downwards
            out.append(grid[r][right])
        right -= 1
        if top <= bottom:                         # a row is still unread
            for c in range(right, left - 1, -1):  # bottom wall, right to left
                out.append(grid[bottom][c])
            bottom -= 1
        if left <= right:                         # a column is still unread
            for r in range(bottom, top - 1, -1):  # left wall, upwards
                out.append(grid[r][left])
            left += 1
    return out

def spiral_unguarded(grid):                       # the same loop without the two ifs
    top, bottom, left, right = 0, len(grid) - 1, 0, len(grid[0]) - 1
    out = []
    while top <= bottom and left <= right:
        out += [grid[top][c] for c in range(left, right + 1)]; top += 1
        out += [grid[r][right] for r in range(top, bottom + 1)]; right -= 1
        out += [grid[bottom][c] for c in range(right, left - 1, -1)]; bottom -= 1
        out += [grid[r][left] for r in range(bottom, top - 1, -1)]; left += 1
    return out

print(spiral([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]))
# [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]
print(spiral([[1, 2, 3]]), spiral([[1], [2], [3]]))
# [1, 2, 3] [1, 2, 3]
print(spiral_unguarded([[1, 2, 3]]))
# [1, 2, 3, 2, 1]
print(spiral_unguarded([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]))
# [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7, 6]

The unguarded version fails on a single row, which you might expect, and also on the 3 × 4 grid, which you might not. After the first lap the unread rectangle is the single row 6 7. The second lap reads it as its top wall, the rectangle is now empty, and the unchecked bottom move reads 6 again. Any grid whose innermost ring is one row or one column thick triggers it.

To test the boundary version, compare it with the other common method: walk cell by cell, turning clockwise whenever the next cell is off the grid or already visited. It is slower to write and needs a seen matrix, but it is hard to get wrong, which is what you want from a reference. Two thousand random grids, from 1 × 1 up to 9 × 9:

import random

def walk(grid):                                   # the other method: turn when blocked
    rows, cols = len(grid), len(grid[0])
    seen = [[False] * cols for _ in range(rows)]
    dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]     # right, down, left, up
    r = c = d = 0
    out = []
    for _ in range(rows * cols):
        out.append(grid[r][c])
        seen[r][c] = True
        nr, nc = r + dirs[d][0], c + dirs[d][1]
        if not (0 <= nr < rows and 0 <= nc < cols) or seen[nr][nc]:
            d = (d + 1) % 4                       # blocked: turn clockwise
            nr, nc = r + dirs[d][0], c + dirs[d][1]
        r, c = nr, nc
    return out

random.seed(9)
ok, unguarded_wrong = True, 0
for _ in range(2000):
    rows, cols = random.randint(1, 9), random.randint(1, 9)
    grid = [[random.randint(0, 99) for _ in range(cols)] for _ in range(rows)]
    ok &= spiral(grid) == walk(grid)
    unguarded_wrong += spiral_unguarded(grid) != walk(grid)
print(ok, unguarded_wrong)                        # True 887

The boundary version agrees on every grid. The unguarded one is wrong on 887 of the 2,000 — not a rare corner case, but close to half of all rectangles.

The complexity

Every cell is appended exactly once, and each loop iteration does work proportional to the cells it outputs, so the time is O(rows × cols). The boundary version uses O(1) extra space besides the output: four integers. The turning walk uses the same time but an extra O(rows × cols) for the seen matrix, unless you overwrite the grid with a marker — which destroys the input and fails if the marker is a legal value.

Where it goes wrong

• Missing the two guards. Shown above: a thin innermost ring is read twice.
• Patching with a cell count. Cutting the unguarded output to rows * cols values happens to give the right answer, because the extra reads only ever come at the very end. It hides the bug instead of explaining it, and an interviewer will ask why the cut is there. Fix the guard.
• Mixing inclusive and exclusive bounds. Here all four bounds are inclusive, so every range ends at bound + 1 or bound - 1. Pick one convention and do not switch halfway through.
• Empty input. grid[0] on an empty list raises an error; check before reading the width.

How to say it in an interview

"I keep four inclusive bounds around the part of the matrix I haven't read. Each lap reads the top row, the right column, the bottom row and the left column, shrinking one bound after each. The bottom and left moves are guarded, because after the first two moves the remaining rectangle can be empty — that's what breaks single rows and thin centres. It's O(rows × cols) time and O(1) extra space."

The same four-bound thinking helps with rotating a matrix in place, which also works ring by ring.