Rotate Image (Matrix by 90 Degrees)
WHAT IT SAYS
Rotate an n x n matrix 90 degrees clockwise, in place, without allocating another matrix.
WHAT IT'S REALLY ASKING
"A rotation is not an exotic motion — it is a permutation of cells, and permutations compose. Reflect the matrix across its main diagonal and every element is already in the right column; it is only facing the wrong way. What single, embarrassingly cheap operation fixes the direction?"
Write into a fresh matrix
O(n^2) time, O(n^2) extra spaceAllocate result[n][n] and copy: result[j][n-1-i] = matrix[i][j]. Then copy the whole thing back over the original. Nothing subtle, and it works.
WHERE THE WORK IS WASTED — The second matrix is not buying you any computation. Every cell's destination is known in O(1) from its coordinates alone — there is nothing to search for, nothing to derive. The copy exists solely to keep a source value alive while its destination gets overwritten. In other words you are allocating n^2 cells to dodge a collision that, at any instant, involves exactly four cells. That is the whole bill: n^2 memory to avoid one temp variable's worth of trouble.
A rotation is two reflections, and reflections are free.
Write the rotation down as a map on coordinates: clockwise 90 sends (i, j) to (j, n-1-i). Now factor it. Transpose sends (i, j) to (j, i). Reversing each row sends (j, i) to (j, n-1-i). Compose them and you land exactly on the rotation. So rotation = transpose, then flip horizontally. That is not a coincidence you have to memorise — it is the standard fact that any rotation is a composition of two reflections, and here the two mirrors are the main diagonal and the vertical midline. But why does factoring make the memory problem disappear? Look at the cycle structure. The rotation permutation is built out of 4-cycles: (i,j) goes to (j,n-1-i) goes to (n-1-i, n-1-j) goes to (n-1-j, i) and back. To move a 4-cycle in place you must stash one value in a temp and rotate the rest through it in a strict order — get the order wrong and you clobber data. Both reflections, by contrast, are made purely of 2-cycles. Transposing pairs (i,j) with (j,i) and nothing else. Reversing a row pairs a cell with its mirror and nothing else. A 2-cycle is just a swap — and a swap is the one permutation every language performs natively with no bookkeeping whatsoever. Factoring the rotation into involutions turns a scary in-place cycle-chasing problem into two loops of swap().
Transpose, then reverse each row
O(n^2) time, O(1) extra space, two passesSwap matrix[i][j] with matrix[j][i] for every j greater than i — the upper triangle only, or you will transpose it twice and undo yourself. Then reverse each row with two pointers walking inwards. Constant extra space and no index formula more complicated than n-1-i.
Chase the 4-cycles directly
O(n^2) time, O(1) space, one pass over the elementsThe direct route: peel the matrix in concentric rings and, for each of the ring's positions, rotate the four corresponding cells with one temp variable. It touches each element exactly once instead of twice, so it is strictly fewer writes — you just pay for it in index arithmetic that is very easy to get wrong under interview pressure.
Factor the Permutation
YOU'LL SEE IT AGAIN WHEN
- You must rearrange a structure in place, and the destination of each element is a closed-form function of its position — the difficulty is collision, not search.
- The rearrangement is geometric (rotate, reverse, shift, mirror) and could plausibly be described as a composition of simpler self-inverse moves.
- The naive fix is 'copy it somewhere safe first', and the copy is asymptotically larger than the number of elements actually in flight at any moment.