Rotate Image
Rotate a square grid 90° in place, by composing two simple operations instead of deriving one hard formula
Problem Statement
Rotate an n × n matrix 90° clockwise, in place. You may not allocate another grid.
Input: [[1,2,3], Output: [[7,4,1],
[4,5,6], [8,5,2],
[7,8,9]] [9,6,3]]
The first COLUMN, read bottom to top, becomes the first ROW.Intuition
The direct approach is to work out where each value lands and move it there:
grid[r][c] → grid[c][n-1-r]That formula is correct and awful to use. Moving one value overwrites another, so you must move four at a time around a cycle, holding one in a temporary — and getting all four index expressions right, first try, is genuinely difficult.
The insight
Do not derive the rotation. Build it from two operations you can each check by eye.
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 3Transpose flips across the diagonal. Reversing each row then flips left-to-right. Together they are exactly a 90° clockwise rotation.
Both steps are in place, so the whole thing is O(1) space.
This is a general habit worth taking away: a transform that is hard to derive is often the composition of two that are not. Verifying two easy steps beats debugging one hard formula.
Approach
Transpose — swap grid[r][c] with grid[c][r]
Start the inner loop at c = r. Starting at 0 swaps every pair twice and leaves the grid unchanged.
Reverse each row
A standard two-pointer reversal, or the language's built-in.
Solution
def rotate(matrix: list[list[int]]) -> None:
"""Rotate an n x n matrix 90 degrees clockwise, in place.
Transpose across the main diagonal, then reverse each row.
"""
n = len(matrix)
# 1. Transpose. c starts at r so each pair is swapped once.
for r in range(n):
for c in range(r, n):
matrix[r][c], matrix[c][r] = matrix[c][r], matrix[r][c]
# 2. Reverse each row.
for row in matrix:
row.reverse()row.reverse() mutates in place. Using row = row[::-1] would rebind the loop variable and leave the matrix untouched — a silent no-op.
`c` must start at `r`
for c in range(r, n): ✓ each pair swapped once
for c in range(n): ✗ each pair swapped twice → unchangedThe second version visits (0,1) and swaps, then later visits (1,0) and swaps back. The matrix returns to its original state and the reversal alone produces a mirror image, not a rotation.
The output looks structured, which makes it easy to mistake for a rotation done in the wrong direction.
Complexity Analysis
Time Complexity
O(n²)
Space Complexity
O(1)
Time — the transpose touches about half the cells, the reversal touches all of them. Both are O(n²), which is the floor: every cell has to move.
Space — only a temporary during each swap. This is the requirement that rules out the obvious "build a new grid" solution.
Edge Cases
Related Problems
- Transpose Matrix — the first half, on its own
- Spiral Matrix — another problem about walking a grid precisely
- Matrix — the rotation table and the in-place techniques