Matrix

01 / The shared mechanism

A matrix isn't a single sequence — it's a 2-D coordinate space where every cell is addressed by two indices that compose in specific ways. The job is finding the right walk order. Three classic sub-patterns: rotate by transpose-then-reverse, spiral by shrinking-boundary loops, and staircase search by walking from a corner where the answer is monotone in both directions.

01 / The one-sentence essence

Keep four boundaries — top, right, bottom, left — and walk the perimeter of the rectangle they enclose. After each of the four legs, shrink that boundary inward by one and loop. The grid is consumed layer by layer until the boundaries cross.

Problemreturn the cells of M in spiral orderM1 2 3 ; 4 5 6 ; 7 8 9

Grid is 3 × 3. Boundaries start at top=0, bottom=2, left=0, right=2. Walk the perimeter, shrink, repeat.

step

0 / 15

cur

—

visited

0 / 9

0 / 15

02 / The pattern signature

# four boundaries enclosing the unvisited rectangletop ← 0;  bottom ← R-1left ← 0;  right ← C-1while top ≤ bottom and left ≤ right:# 1) left → right along topfor c in left..right: visit(top, c)top ← top + 1# 2) top → bottom along rightfor r in top..bottom: visit(r, right)right ← right − 1if top ≤ bottom:# 3) right → left along bottomfor c in right..left: visit(bottom, c)bottom ← bottom − 1if left ≤ right:# 4) bottom → top along leftfor r in bottom..top: visit(r, left)left ← left + 1

03 / When to recognize this pattern

"spiral order traversal"

LC 54. The canonical use — output every cell in spiral order. Four boundary pointers, four directional passes, shrink after each. O(R · C) time with each cell visited exactly once.

"fill matrix in spiral order"

LC 59. Same walk, opposite direction — instead of reading values you write 1, 2, 3, …, n² as you go. The boundary scaffolding is identical; only the visit step changes from read to write.

"layer-by-layer rotation / processing"

Anything that decomposes naturally into concentric rings — rotating each ring in place, image-style filters that touch a layer at a time, perimeter counting. The four-boundary frame just iterates one layer; wrap it in an outer loop over layers.

"matrix perimeter problems"

When the question is about cells on the border of a rectangle (or a sub-rectangle), the spiral walk hands you them in one pass. Useful for boundary-sum, ring queries, and spiral-coordinate puzzles (LC 885, LC 2326).

04 / Common pitfalls

Skipping the conditional checks before passes 3 and 4.

When only one row or one column remains, the third pass (R→L along the bottom) would revisit the row the first pass already drained — and the fourth would do the same with the column. Guard pass 3 with top ≤ bottom and pass 4 with left ≤ right. Without these checks, non-square inputs print duplicates.

ii.

Off-by-one on the boundary updates.

Each boundary advances after its pass — top++ after the L→R walk, right−− after the T→B walk, and so on. Easy to write top++ in the wrong place (before the pass, or in the wrong direction), which collapses the rectangle and either drops a row or revisits one.

iii.

Writing four separate index loops instead of one walk pointer.

A common cleaner variant: keep (r, c) plus a direction index d ∈ {0,1,2,3} with dr/dc arrays. Step; if you'd step outside the current boundary, rotate d ← (d + 1) % 4 and shrink the boundary you just left. One loop, one termination condition — fewer places to make a mistake than four near-duplicate for loops.

05 / Go practice — on LeetCode

Four problems on the spiral walk. The first two are direct — read vs. write. The last two generalize the walk to non-trivial start points and to a linked-list output.

01Spiral Matrix— LC 54medium→02Spiral Matrix II— LC 59medium→03Spiral Matrix III— LC 885medium→04Spiral Matrix IV— LC 2326medium→

— / When to use which

rotate in place

Use when the question is about a geometric transform of the grid itself — 90° / 180° rotation, transpose, mirror. Decompose into two passes (transpose + row-reverse) so it's in place with no extra grid.

transpose + reverse · LC 48

spiral traversal

Use when you have to visit every cell along the perimeter of a shrinking rectangle — output in spiral order, fill in spiral order, count layers. Maintain four boundaries that collapse inward each lap.

four boundaries · LC 54 · LC 59

staircase search

Use when the matrix is monotone along both rows and columns and you're looking for a value. Start from a corner where one direction strictly increases and the other strictly decreases — every comparison rules out a full row or column.

top-right walk · LC 240 · O(N + M)