VFlash: Fast, Accurate Visual Planning via Flash Primitive Decoding
u_Unrolled
DSA for AI/ML · Module 01: Arrays and strings

Lesson 1.12 of 16 in this moduleFree

Spiral Matrix

Read a matrix in spiral order: from a visited-grid walk that turns at walls, to four shrinking boundaries with O(1) extra space, and the guards that stop single rows and columns being read twice. Then generating spirals, layers and diagonal orders.

about 10 min 3 Python examples 2 quick checks

Problem. Given an m × n matrix, return its elements in spiral order: clockwise from the top-left, moving inwards.

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

ML context. This is the cleanest exercise in traversal order over a 2D grid, which matters whenever layout meets computation: tiled matrix multiplication, patch extraction for vision transformers, space-filling orders for cache-friendly access, and reading feature maps layer by layer. The real skill tested is boundary bookkeeping: getting the edges exactly right.

There's no faster algorithm to find: every cell must be read once, so O(m · n) is optimal. The lesson is about memory and correctness.


1. Step 1: Clarify

Question Answer Why it matters
Rectangular? Yes, m × n, possibly 1 × n or m × 1 Single rows and columns are the bug magnets
Empty matrix? Possible Return []
Modify the input? No Rules out marking visited cells inside it
Size? Up to 10 × 10 here, 10⁴ × 10⁴ in general Decides whether O(m · n) extra memory is acceptable

2. Step 2: Brute force: simulate with a visited grid

Walk like a robot: go right until you'd hit a wall or a visited cell, then turn clockwise. A separate visited grid remembers where you've been.

python
def spiral_visited(m):
    if not m or not m[0]:
        return []
    rows, cols = len(m), len(m[0])
    visited = [[False] * cols for _ in range(rows)]          # O(m · n) extra
    dr, dc = [0, 1, 0, -1], [1, 0, -1, 0]                     # right, down, left, up
    r = c = d = 0
    out = []
    for _ in range(rows * cols):
        out.append(m[r][c])
        visited[r][c] = True
        nr, nc = r + dr[d], c + dc[d]
        if not (0 <= nr < rows and 0 <= nc < cols) or visited[nr][nc]:
            d = (d + 1) % 4                                   # turn clockwise
            nr, nc = r + dr[d], c + dc[d]
        r, c = nr, nc
    return out


M = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]
assert spiral_visited(M) == [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]
assert spiral_visited([[1, 2, 3]]) == [1, 2, 3]
assert spiral_visited([[1], [2], [3]]) == [1, 2, 3]
print("visited-grid walk works: O(m · n) time, O(m · n) extra space")

O(m · n) time is already optimal. But the visited grid costs O(m · n) extra memory: a 10⁴ × 10⁴ boolean grid is 100 million entries. Can we know where the walls are without remembering every cell?


3. Step 3: Optimise: four shrinking boundaries

First principles. The visited cells always form complete outer rows and columns. So the unvisited region is always a rectangle, described by just four numbers: top, bottom, left, right. Read one side, then move that boundary inwards.

the 3 by 4 matrix coloured by pass: the top row, then the right column, then the bottom row backwards, then the left column upwards, then the inner block; the output is 1 2 3 4 8 12 11 10 9 5 6 7.
Diagram— the 3 by 4 matrix coloured by pass: the top row, then the right column, then the bottom row backwards, then the left column upwards, then the inner block; the output is 1 2 3 4 8 12 11 10 9 5 6 7.
five frames where each side read moves one boundary inwards: top 0 to 1, right 3 to 2, bottom 2 to 1, left 0 to 1, and the last top row stops once top exceeds bottom.
Diagram— five frames where each side read moves one boundary inwards: top 0 to 1, right 3 to 2, bottom 2 to 1, left 0 to 1, and the last top row stops once top exceeds bottom.
python
import random


def spiral(m):
    if not m or not m[0]:
        return []
    top, bottom, left, right = 0, len(m) - 1, 0, len(m[0]) - 1
    out = []
    while top <= bottom and left <= right:
        for c in range(left, right + 1):              # top row →
            out.append(m[top][c])
        top += 1
        for r in range(top, bottom + 1):              # right column ↓
            out.append(m[r][right])
        right -= 1
        if top <= bottom:                             # guard: a row is left
            for c in range(right, left - 1, -1):      # bottom row ←
                out.append(m[bottom][c])
            bottom -= 1
        if left <= right:                             # guard: a column is left
            for r in range(bottom, top - 1, -1):      # left column ↑
                out.append(m[r][left])
            left += 1
    return out


def spiral_visited(m):
    if not m or not m[0]:
        return []
    rows, cols = len(m), len(m[0])
    seen = [[False] * cols for _ in range(rows)]
    dr, dc = [0, 1, 0, -1], [1, 0, -1, 0]
    r = c = d = 0
    out = []
    for _ in range(rows * cols):
        out.append(m[r][c])
        seen[r][c] = True
        nr, nc = r + dr[d], c + dc[d]
        if not (0 <= nr < rows and 0 <= nc < cols) or seen[nr][nc]:
            d = (d + 1) % 4
            nr, nc = r + dr[d], c + dc[d]
        r, c = nr, nc
    return out


M = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]
assert spiral(M) == [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]
rng = random.Random(26)
for _ in range(500):
    rows, cols = rng.randint(1, 6), rng.randint(1, 6)
    m = [[r * cols + c for c in range(cols)] for r in range(rows)]
    assert spiral(m) == spiral_visited(m)
    assert sorted(spiral(m)) == list(range(rows * cols))       # every cell exactly once
print("four boundaries: O(m · n) time, O(1) extra, matches the walk on 500 shapes")
  • Time: O(m · n): each cell is read once. Extra space: O(1) (besides the output).
  • Why the two guards: after reading the top row and right column, the remaining rectangle may be empty. For a single row like [[1, 2, 3]], without the top <= bottom check the "bottom row ←" loop would read 3, 2, 1 again.

Quick check

What goes wrong on a single-row matrix [[1, 2, 3]] if you drop the top <= bottom guard?

  1. Nothing
  2. After reading the top row, top > bottom, but the bottom-row loop still runs and reads the same row backwards, giving duplicates
  3. It raises an IndexError on every input
  4. The output is reversed
Show the answer

B. After reading the top row, top > bottom, but the bottom-row loop still runs and reads the same row backwards, giving duplicates — The guard checks that a distinct bottom row still exists before reading it.


4. When the constraints change

If the constraint becomes… Best approach Time Extra space
Classic read-out Four shrinking boundaries O(m·n) O(1)
Simplest to get right under pressure Direction-turning walk with a visited grid O(m·n) O(m·n)
May modify the input Walk and mark visited cells with a sentinel O(m·n) O(1)
Generate an n × n spiral of 1..n² Same boundaries, writing instead of reading O(n²) O(n²) output
Counter-clockwise or another start corner Same idea, different side order O(m·n) O(1)
Only the k-th element Skip whole layers: each layer has 2(h + w) − 4 cells O(min(m, n)) O(1)

Change A: generate a spiral instead of reading one

The same four boundaries, but now write 1, 2, 3, … into an empty grid. Reading and writing are the same traversal: once the order is right, the action at each cell is just a detail.

python
def generate_spiral(n):
    m = [[0] * n for _ in range(n)]
    top, bottom, left, right = 0, n - 1, 0, n - 1
    k = 1
    while top <= bottom and left <= right:
        for c in range(left, right + 1):
            m[top][c] = k; k += 1
        top += 1
        for r in range(top, bottom + 1):
            m[r][right] = k; k += 1
        right -= 1
        if top <= bottom:
            for c in range(right, left - 1, -1):
                m[bottom][c] = k; k += 1
            bottom -= 1
        if left <= right:
            for r in range(bottom, top - 1, -1):
                m[r][left] = k; k += 1
            left += 1
    return m


assert generate_spiral(3) == [[1, 2, 3], [8, 9, 4], [7, 6, 5]]
assert generate_spiral(1) == [[1]]
print("generating a spiral reuses the same boundaries")

Change B: jump straight to the k-th element

Each full layer of an h × w rectangle has 2(h + w) − 4 cells (or h · w if it's a single row or column). Skip whole layers until k falls inside one, then walk only that layer: O(min(m, n)) layer skips plus at most one layer's walk, instead of reading everything.

Change C: diagonal or zig-zag order

Other traversal orders follow the same discipline: describe what remains with a few indices, and write the turning rule down before coding. (A zig-zag over diagonals uses r + c = constant per diagonal.)

Quick check

What's the core idea that removes the visited grid?

  1. The unvisited cells always form a rectangle, so four boundary indices describe exactly what's left
  2. Sorting the matrix
  3. Reading the matrix twice
  4. Using recursion
Show the answer

A. The unvisited cells always form a rectangle, so four boundary indices describe exactly what's left — Because the spiral peels off whole rows and columns, the remaining region stays a rectangle.


5. Saying it out loud

"Every cell has to be read, so O(m·n) is optimal. A walk that turns at walls and visited cells works but needs an O(m·n) visited grid. Since the unvisited region is always a rectangle, I'll keep top, bottom, left and right, read one side at a time and shrink that boundary, with guards before the bottom row and left column so single rows or columns aren't read twice. O(1) extra space."


Check yourself

  1. Why can't spiral order be faster than O(m · n)?
  2. What does the visited grid cost, and what replaces it?
  3. Why does the unvisited region stay a rectangle?
  4. Which two reads need guards, and why?
  5. How do you generate a spiral of 1..n²?
  6. How many cells are in one full layer of an h × w rectangle?
Answers
  1. The output contains all m · n values, and each must be read.
  2. O(m · n) extra memory; four boundary indices describe the remaining region.
  3. Each pass removes a complete outer row or column.
  4. The bottom row (needs top <= bottom) and the left column (needs left <= right): after the first two sides, the remaining rectangle may be empty, and reading would repeat cells.
  5. Run the same boundary loop, writing an increasing counter instead of reading.
  6. 2(h + w) − 4 when h, w ≥ 2 (h · w for a single row or column).