Rotate Image
Rotate Image: rotate an n × n matrix 90° clockwise in place (no extra matrix).
- n == matrix.length == matrix[i].length
- 1 <= n <= 20
- -1000 <= matrix[i][j] <= 1000
Intuition
Rotate image leetcode problem 48 rotates an n × n matrix 90 degrees clockwise, in place. The in-place requirement rules out building a rotated copy and is the whole challenge.
Rather than working out where each element lands, the rotation decomposes into two simple operations:
- Transpose the matrix, then reverse each row — the composition of those two is exactly a 90-degree clockwise rotation.
Transposing swaps matrix[i][j] with matrix[j][i], reflecting across the main diagonal. Reversing each row then reflects horizontally. Two reflections across intersecting axes produce a rotation, which is why this works.
The detail that ruins implementations is the transpose loop bounds. The inner loop must start at j = i, not j = 0:
Swapping every pair twice returns the matrix to its original state, so a full double loop silently does nothing. Only the upper triangle should be traversed.
The order of the two operations is equally load-bearing. Transpose then reverse rows gives clockwise; reverse rows then transpose gives anticlockwise. Both look plausible, and the wrong order fails on any non-symmetric input.
For anticlockwise rotation, transpose then reverse each column instead — worth knowing since the variant appears often.
The layer-by-layer approach is the alternative: rotate four elements at a time in concentric rings, moving each directly to its destination. It is a single pass rather than two, but the index arithmetic is error-prone for no real gain.
Both are O(n²) time — unavoidable, since every element must move — with O(1) extra space.
Transpose, then reverse each row — two simple passes replacing one confusing four-way cycle. Recognising that a rotation decomposes into a reflection across the diagonal followed by a horizontal flip is the trick worth keeping; the anticlockwise rotation is the same pair with the reverse applied to columns instead.
Approach
Before reading on: price up what the brute force costs here, then ask whether the traversal can carry its state across rows instead of restarting. Aim for O(n²) time and O(1) space.
Decompose the rotation
Transpose, then reverse each row. Two reflections across intersecting axes compose into a rotation, which is why this simple pair works.
Transpose the upper triangle only
Start the inner loop at j = i, not 0. Swapping every pair twice restores the original matrix, so a full double loop does nothing at all.
Reverse each row
After transposing, reversing rows completes the clockwise rotation. Each row reverses independently with two pointers.
Respect the operation order
Transpose then reverse gives clockwise; the reverse order gives anticlockwise. Both look plausible and the wrong one fails on non-symmetric input.
Know the anticlockwise variant
For anticlockwise, transpose then reverse each column rather than each row. The variant appears often enough to be worth remembering.
Cost of the approach
Every element is touched a constant number of times, giving O(n²) time — unavoidable — with O(1) extra space as required.
Solution & live demo
Common pitfalls
Transposing over the full index range
for i in range(n):
for j in range(n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]for i in range(n):
for j in range(i + 1, n):Every pair is swapped twice — once as (i, j) and once as (j, i) — which returns the matrix to its original state. Iterating only above the diagonal touches each pair exactly once.
Reversing before transposing
for row in matrix: row.reverse() # then transpose
# transpose for row in matrix: row.reverse()
The two operations don't commute — reversing first produces a 90° anticlockwise rotation. Order is the entire difference between the two directions.
Building a new matrix
return [list(row) for row in zip(*matrix[::-1])]
# swap in place, then reverse rows
Elegant, but the problem requires modifying the input in place with O(1) extra space. Returning a new grid also leaves the caller's matrix unchanged, so the expected output never appears.
Edge cases
Transpose and row-reverse are both no-ops; the single cell is unchanged, as a rotation should leave it.
One diagonal swap plus two row reversals produce the correct 90° turn.
Restricting the transpose to j > i ensures each off-diagonal pair is swapped exactly once.