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
A 90° clockwise rotation factors into transpose + reverse each row — two clean in-place passes whose composition is exactly the rotation, with no extra grid.
Problemrotate the matrix 90° clockwise, in placeM3×3
Square matrix of size 3×3. We'll rotate 90° clockwise in place by transpose, then reverse each row.
step
0 / 11
phase
input
swaps left
—
0 / 11
02 / The pattern signature
# phase 1 — transpose: swap m[i][j] with m[j][i] for i < jfor i in 0..n-1:for j in i+1..n-1:m[i][j], m[j][i] ← m[j][i], m[i][j]# phase 2 — reverse each rowfor i in 0..n-1:for j in 0..n/2-1:m[i][j], m[i][n-1-j] ← m[i][n-1-j], m[i][j]# composition ≡ 90° clockwise rotation; O(N²) total, O(1) extra
03 / When to recognize this pattern
"rotate image / matrix by 90°"
The canonical case — LC 48. Don't allocate a second grid: do
transpose then reverse-each-row and the math falls out."transpose a matrix"
LC 867 — phase 1 in isolation. The same loop nest, just stop before reversing. Worth recognizing in isolation so you know the building block when you see it.
"flip / mirror"
Anti-clockwise 90° = reverse rows first, then transpose (or equivalently transpose + reverse columns). Same two primitives, swapped order or axis — pick the form that keeps both passes in place.
"layer-by-layer rotation"
The alternative O(1)-extra approach: rotate concentric layers as 4-way cycles (top ← left ← bottom ← right ← top). Same complexity, but the index arithmetic is brittle. Reach for it only when you need the single-pass form.
04 / Common pitfalls
i.
Iterating the full square in the transpose instead of
i < j.The transpose swaps each pair once. If your inner loop runs
j from 0 to n-1, each pair gets swapped twice and you end up with the original matrix again. Always restrict to j > i (the strict upper triangle).ii.
Confusing clockwise with anti-clockwise.
Clockwise = transpose + reverse-rows. Anti-clockwise = transpose + reverse-columns (equivalently: reverse-rows + transpose). It's easy to ship the wrong direction; sanity-check on a 2×2 like
[[1,2],[3,4]] — clockwise should give [[3,1],[4,2]].iii.
Trying to do it in one pass without extra space.
It's possible (the 4-way cycle / layer-by-layer trick), but the index arithmetic is fiddly and easy to get off by one. The two-phase form is the cleanest: each pass is a one-line swap loop, and their composition is the rotation. Use one pass only when you must.
05 / Go practice — on LeetCode
Four problems. The first is the textbook 90° rotation; the next three exercise the same primitives (transpose, row-reverse) and the think of grid ops as compositions habit.
— / 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)