Pattern 2: In-place transformation
Transforming a matrix without using another matrix (O(1) extra space) is a kind of problem that seems to require a copy — but index tricks solve it. Two classics: rotating the image and zeroing rows/columns.
Try it first: Rotate Image
Before reading the theory, try to solve it. You can start with brute force, you can fail — the point is to feel the problem. The theory comes right below.
Given an n × n matrix, rotate it 90° clockwise, in place (without using another matrix). Return the rotated matrix.
Example: [[1,2,3],[4,5,6],[7,8,9]] → [[7,4,1],[8,5,2],[9,6,3]].
Tried it? Copying into a new rotated matrix works, but it costs O(n²) of memory. The theory below rotates in place with two simple steps.
Theory 1: rotating = transpose + reverse
Rotating 90° clockwise looks complicated to do in place — but it decomposes into two easy operations:
- Transpose: mirror across the main diagonal (swap
m[i][j]withm[j][i]). Rows become columns. - Reverse each row: mirror horizontally.
1 2 3 transpose 1 4 7 reverse rows 7 4 1
4 5 6 ───────────▶ 2 5 8 ──────────────▶ 8 5 2
7 8 9 3 6 9 9 6 3
Work it out with one cell to convince yourself: the 1 at (0,0) stays at
(0,0) in the transpose and then goes to (0,2) when the row is reversed —
exactly where the 1 should be after rotating 90°. The two steps compose the
rotation.
A detail that avoids a classic bug: in the transpose, j starts at i + 1. If
you walked the whole matrix, you would swap each pair twice and go back to
the original. Swapping only the half above the diagonal makes each swap happen
once. O(n²) time (touches each cell once), O(1) space.
Theory 2: using the matrix itself as a scratchpad
Set Matrix Zeroes: if a cell is 0, zero out its entire row and column. The danger is doing this "on the fly" — the first 0 would zero cells that, read later, would trigger false zeros in a cascade.
The naive solution marks in an auxiliary matrix (O(m·n) space) which rows and columns to zero. The in-place trick: use the matrix's own first row and first column as the markers — they become the "scratchpad". That way the extra space drops to O(1).
1. In one pass, for each 0 at (r,c): mark grid[r][0]=0 and grid[0][c]=0
(and remember separately whether the 1st row/column originally had any 0).
2. In a second pass, zero grid[r][c] if grid[r][0]==0 or grid[0][c]==0.
3. Finally, zero the 1st row/column if they needed it.
O(m·n) time (a few passes), O(1) space — because the markers live inside the matrix itself.
The lesson that generalizes
In-place transformation almost always comes from two ideas: (1) decomposing the hard transformation into simple, reversible steps (transpose + reverse), and (2) reusing the data's own space as auxiliary memory (the 1st row/column as markers). When the statement asks for "O(1) space", ask: "what simple structure composes this?" and "can I take notes inside the input itself?".
🧠 Review quiz
0/41. How do you rotate a matrix 90° clockwise, in place?
2. In the in-place transpose, why does the inner loop start at j = i + 1?
3. In Set Matrix Zeroes, what is the trick to use O(1) extra space?
4. Why can you NOT zero the row and column 'on the fly' when you find a 0?
Summary
- Rotate the image: transpose + reverse each row → 90° clockwise, O(n²)/O(1).
- Set Matrix Zeroes: mark in the 1st row/column themselves, then zero → O(m·n)/O(1).
- In-place comes from decomposing the transformation and reusing the data's own space.
Next lesson: treating the grid as a graph and flooding regions — DFS.