Matrix / 2-D Grids

A 2-D grid (a matrix) is just an array of arrays: you address a cell by its (row, col) pair, where grid[r][c] is the value in row r, column c. Most grid problems are about traversal order — and the trickiest classic is the spiral: read the outer boundary, then peel inward.

The trick is never tracking which individual cells are visited — the four bounds are the visited set. Everything outside them is already collected.

Intuition

Picture peeling an onion. The outermost ring is the boundary of the grid; once you have read every cell on it, that ring is gone and a smaller grid sits inside. The four bounds describe the rectangle of cells you have not peeled yet. Each lap reads one full ring and tightens the box by one cell on the side you just finished.

Because each side-walk hands off cleanly to the next (top row ends where the right column begins), you trace one continuous spiral without ever revisiting a cell or stepping out of bounds.

Walk through it

Step through the animation on the right. The r,c pointer rides the cell currently being read, and the order label at the bottom collects the spiral.

First the top row goes left to right: 1 2 3. Now top moves down to row 1. The right column goes top to bottom over the remaining rows: 6 9. Now right moves left. The bottom row goes right to left: 8 7. Now bottom moves up. The left column goes bottom to top: 4. Now left moves right. The bounds have closed in to a single cell — the center 5 — which we read last. Final order: 1 2 3 6 9 8 7 4 5.

The code, line by line

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

• The four bounds box the unvisited rectangle; the while runs as long as a non-empty box remains.
• The first for walks the top row left to right, then top += 1 retires that row.
• The second for walks the right column top to bottom, then right -= 1 retires that column.
• The if top <= bottom guard before the bottom row prevents re-reading a row already consumed when the box has collapsed to a single row.
• The if left <= right guard before the left column does the same for a single-column box.
• When the bounds cross, the box is empty and res holds the full spiral.

Complexity

There is no nested re-scanning: each cell is appended to res a single time, so the work is linear in the number of cells, m·n. The bounds are four integers, so the bookkeeping is constant extra space (the output list itself is not counted).

When to use / pitfalls

Practice