Rotate Image
You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise). You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
- n == matrix.length == matrix[i].length
- 1 <= n <= 20
- -1000 <= matrix[i][j] <= 1000
matrix = [[1,2,3],[4,5,6],[7,8,9]][[7,4,1],[8,5,2],[9,6,3]]matrix = [[1,2],[3,4]][[3,1],[4,2]]matrix = [[1]][[1]]A matrix here is a square grid of numbers. Cell (i, j) means row i, column j, with rows counted top to bottom and columns left to right, both from 0. Before touching code, work out where each cell must go. Rotate the grid 90° clockwise and watch a whole row: the top row stands up and becomes the rightmost column (its first element on top). In general, row i lands in column n - 1 - i, and a cell's position along its row becomes its position down that column. So the mapping is: (i, j) moves to (j, n - 1 - i). Sanity-check a corner: the top-left (0, 0) moves to (0, n-1) — the top-right. Correct.
With that mapping, rotation into a fresh matrix is one loop:
new_matrix = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
new_matrix[j][n - 1 - i] = matrix[i][j]
for i in range(n):
matrix[i] = new_matrix[i][:]The problem forbids exactly this — no second matrix. And in-place rotation is genuinely awkward if attacked directly: writing a value into its destination overwrites a value that has not moved yet. (Cells actually rotate in cycles of four: (i, j) displaces (j, n-1-i), which displaces the next, and the fourth loops back — doable, but the index bookkeeping is fiddly and error-prone under interview pressure.)
Here is the elegant escape: a 90° rotation is exactly the composition of two flips, and each flip is trivially in-place because it just swaps pairs of cells. First, transpose — reflect across the main diagonal, sending (i, j) to (j, i); rows become columns. Second, reverse every row — a horizontal mirror, sending (j, i) to (j, n - 1 - i). Chain them: (i, j) goes to (j, i), then to (j, n - 1 - i) — precisely the rotation mapping derived above. Not a coincidence to memorize; a one-line proof you can re-derive at the whiteboard.
n = len(matrix)
for i in range(n):
for j in range(i + 1, n): # j starts at i+1: touch each pair once
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
for row in matrix: # then mirror every row
row.reverse()The inner loop starting at j = i + 1 matters: transposing means swapping the pair (i, j) and (j, i). Loop over the whole grid and every pair gets swapped twice — back to where it started. Sweeping only above the diagonal touches each pair exactly once.
After transpose (flip across the main diagonal — rows become columns):
[1, 4, 7]
[2, 5, 8]
[3, 6, 9]
After reversing each row (horizontal mirror):
[7, 4, 1]
[8, 5, 2]
[9, 6, 3]
Check cell by cell: 1 went from (0,0) to (0,2); 8 went from (2,1) to (1,2). Both match (i, j) to (j, n-1-i).
Cost is O(N²) time — every cell must move, so that is optimal — and O(1) extra space: two flips, each pure swaps. The reusable idea is decomposition: a transformation that is hard to perform directly may be a chain of trivially-safe steps. It generalizes on the spot — counter-clockwise rotation is the transpose followed by reversing each column (or reverse rows first, then transpose); 180° is two 90° turns, or reverse rows and columns. Derive, don't memorize.
Rotation Sequence
Initial matrix. Goal: Rotate 90° clockwise in-place.
DIAGONAL SYMMETRY
Transposing swaps (i, j) with (j, i). This swaps the x and y axes, preparing the grid for its final rotated state.
MEMORY LIMITS
By performing these flips in-place, we use O(1) extra space. This is critical for large datasets like HD images.