Spiral Matrix

Spiral Matrix asks you to read a 2D grid in a spiral. There is no clever data structure here — the whole challenge is bookkeeping: tracking four moving boundaries cleanly so you visit every cell exactly once, in the right order.

The slow way first

You could try to "walk a robot" around the grid: keep a direction (right, down, left, up), step forward, and turn whenever you hit an edge or a cell you already visited. That works, but it needs a separate visited grid (extra O(m·n) space) and fiddly turn logic — easy to get an off-by-one wrong on the turns.

The question to ask: what stays simple as the spiral shrinks? The answer is the rectangle of unvisited cells. If I track its four edges, I never need a visited grid at all.

The idea: four shrinking boundaries

Keep four indices: top, bottom, left, right — the edges of the rectangle still to be read. Each pass peels one layer:

1. Walk the top row left→right, then push top down.
2. Walk the right column top→bottom, then push right left.
3. Walk the bottom row right→left, then push bottom up.
4. Walk the left column bottom→top, then push left right.

Repeat while top <= bottom and left <= right. The box shrinks each loop until it is empty.

The two if guards (if top <= bottom, if left <= right) matter for non-square or odd-sized grids: after peeling the top and right, the box may already be empty, and we must not re-read a row or column.

Walk through it

Step through the animation on the 3x3 grid. Ring one peels 1, 2, 3 (top), 6, 9 (right), 8, 7 (bottom), 4 (left). Now all four boundaries collapse onto the center. One more loop reads the lone center cell 5, then top passes bottom and we stop — giving [1, 2, 3, 6, 9, 8, 7, 4, 5].

Pseudocode

result = empty list
top, bottom = 0, last row
left, right = 0, last column
while top <= bottom and left <= right:
    walk left..right across row "top", append each      # top row
    top += 1
    walk top..bottom down column "right", append each    # right column
    right -= 1
    if top <= bottom:                                    # bottom row (guard)
        walk right..left across row "bottom", append each
        bottom -= 1
    if left <= right:                                    # left column (guard)
        walk bottom..top up column "left", append each
        left += 1
return result

The Python solution

def spiral_order(matrix):
    result = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    while top <= bottom and left <= right:
        for c in range(left, right + 1):
            result.append(matrix[top][c])
        top += 1
        for r in range(top, bottom + 1):
            result.append(matrix[r][right])
        right -= 1
        if top <= bottom:
            for c in range(right, left - 1, -1):
                result.append(matrix[bottom][c])
            bottom -= 1
        if left <= right:
            for r in range(bottom, top - 1, -1):
                result.append(matrix[r][left])
            left += 1
    return result

• top, bottom, left, right are the four edges of the rectangle that still needs reading.
• The while condition is the heart: as soon as the box is empty (boundaries cross), we stop.
• Top row goes left → right; right column goes top → bottom (note top was already bumped).
• Bottom row goes right → left (a reversed range with step -1); left column goes bottom → top.
• The two if guards prevent re-reading a row or column once the box has shrunk to a single line.

Complexity

We touch each of the m·n cells exactly once, so time is O(m·n) — unavoidable, since the output lists every element. The boundary approach uses only O(1) extra space (ignoring the output list), beating the robot-walk that needs an O(m·n) visited grid.

When this pattern shows up

Practice