Matrix — Algorhythm<br>Matrix

01 / The shared mechanism<br>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.

02 / The one-sentence essence<br>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.

animationcomplexity

Problemrotate the matrix 90° clockwise, in placeM3×3?<br>123456789Square matrix of size 3×3. We'll rotate 90° clockwise in place by transpose, then reverse each row.

step<br>0 / 11

phase<br>input

swaps left

0.5×1×2×<br>0 / 11

matrix<br>default 3×32×24×45×5negatives

03 / The pattern signature<br># phase 1 — transpose: swap m[i][j] with m[j][i] for i for 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

04 / When to recognize this pattern<br>"rotate image / matrix by 90°"<br>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"<br>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"<br>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"<br>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.

05 / Common pitfalls<br>Iterating the full square in the transpose instead of i .<br>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).

Confusing clockwise with anti-clockwise.<br>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]].

Trying to do it in one pass without extra space.<br>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.

06 / Go practice — on LeetCode<br>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.<br>01Rotate Image— LC 48medium→02Transpose Matrix— LC 867easy→03Flipping an Image— LC 832easy→04Minimum Operations to Make a Uni-Value Grid— LC 2033medium→

— / When to use which<br>rotate in place<br>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.<br>transpose + reverse · LC 48

spiral traversal<br>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.<br>four boundaries · LC 54 · LC 59

staircase search<br>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.<br>top-right walk · LC 240 · O(N + M)