Rotate an n × n matrix 90 degrees clockwise, in place.
Restating the Problem: You are given a 2D square matrix (like a photo or a checkerboard). You need to rotate it 90 degrees to the right. However, you are not allowed to create a new matrix to hold the answer; you must modify the given matrix directly.
Constraints to note:n is up to 20, which is very small, but you must do it in place (using O(1) extra memory).
Edge cases:n = 1 is an immediate return. Elements can be negative.
The naive approach is to allocate a new n × n matrix, then iterate through the original matrix, copying matrix[i][j] to its new rotated position in the new matrix. After filling the new matrix, you copy all elements back to the original matrix. This requires O(n^2) extra space, which violates the "in place" requirement. We need a way to move elements without a full scratchpad.
Transposing turns rows into columns: the top row 1 2 3 becomes the left column. A clockwise rotation should put the top row into the right column instead. Reversing each row flips left to right, moving that column to where it belongs.
Anticlockwise is the mirror: transpose, then reverse each column — or equivalently reverse the rows' order first and then transpose.
Worth deriving both once so you are not guessing under pressure.
class Solution: def rotate(self, matrix: List[List[int]]) -> None: n = len(matrix) # 1. transpose — swap across the main diagonal for i in range(n): # (1) for j in range(i + 1, n): # (2) j starts at i+1 matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] # (3) # 2. reverse each row for row in matrix: # (4) row.reverse()
ts
function rotate(matrix: number[][]): void { const n = matrix.length; for (let i = 0; i < n; i++) { // (1) for (let j = i + 1; j < n; j++) { // (2) [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]]; // (3) } } for (const row of matrix) row.reverse(); // (4)}
Turning a square grid a quarter turn clockwise is the same as two simpler moves: flip it across its main diagonal, then reverse each row.
(1) Go through each row i.
(2) Only visit cells to the right of the diagonal, where j > i. Each swap handles a pair of cells, (i, j) and (j, i). If j started at 0, every pair would be swapped twice, which puts everything back where it started.
(3) Swap the cell with its mirror across the diagonal. This is called a transpose: rows become columns. Row 0 becomes column 0, and so on.
(4) Reverse each row. After the transpose, the first column of the original is in the first row, but in the wrong order for a clockwise turn. Reversing every row fixes that. Check it on the top-left corner: it must end up in the top-right corner. The transpose leaves it in place, and the reverse moves it to the end of row 0, the top-right. ✓
Take the 3 × 3 grid [[1, 2, 3], [4, 5, 6], [7, 8, 9]].
After
Grid
start
1 2 3 · 4 5 6 · 7 8 9
transpose
1 4 7 · 2 5 8 · 3 6 9
reverse rows
7 4 1 · 8 5 2 · 9 6 3
The result is the original turned a quarter turn clockwise.
Code Walkthrough:
Step 1 (Transpose): We loop over the rows with index i. For each row i, we loop j from i + 1 to n - 1. We swap matrix[i][j] with matrix[j][i]. This essentially turns rows into columns by reflecting elements across the top-left to bottom-right diagonal.
Step 2 (Reverse Rows): We loop over every row in the now-transposed matrix and reverse it. This reflects the matrix horizontally.
j starts at i + 1, not at 0. This is the only thing here that can be wrong. Looping j from 0 would swap every pair twice, undoing the transpose and leaving the matrix unchanged. Starting at i + 1 visits each pair above the diagonal exactly once.
Diagonal elements are never touched, which is correct — they stay where they are under a transpose.
row.reverse() is in-place in both languages, so no extra memory is used.
O(n^2) time — every element is touched a constant number of times. O(1) extra space.
Time Complexity:O(n^2). The transpose visits about half the elements (since we only loop j from i+1), and the reverse visits all elements. Both operations are proportional to the number of cells in the grid, which is n^2.
Space Complexity:O(1). We do everything by swapping elements in place, requiring no extra memory proportional to n.
O(n^2) is optimal, since every one of the n^2 elements has to move.
There is a direct method that rotates four elements at a time, walking inward ring by ring:
python
for layer in range(n // 2): first, last = layer, n - 1 - layer for i in range(first, last): offset = i - first top = matrix[first][i] matrix[first][i] = matrix[last - offset][first] matrix[last - offset][first] = matrix[last][last - offset] matrix[last][last - offset] = matrix[i][last] matrix[i][last] = top
Same complexity, one pass instead of two — and far harder to get right, because there are four index expressions that must all agree.
Write the transpose-and-reverse version. Mention this one exists if asked whether you can do it in a single pass.
The transpose trick is a small toolkit for matrix problems:
operation
recipe
rotate 90° clockwise
transpose, reverse each row
rotate 90° anticlockwise
transpose, reverse each column
rotate 180°
reverse rows and reverse each row
mirror horizontally
reverse each row
mirror vertically
reverse the row order
Spiral Matrix — a different traversal of the same grid. 4.28.2.
Set Matrix Zeroes — in-place again, using the first row and column as storage. 4.28.3.
Real graphics — a rotation is a matrix multiplication, and Volume II Part 4 derives why. Image libraries do exactly this for the 90-degree cases because it needs no arithmetic on the pixel values.
"Why does transpose plus reverse give a rotation?" Transposing sends the top row to the left column; reversing each row moves it to the right column, which is where a clockwise rotation puts it.
"Why does j start at i + 1?" Otherwise every pair is swapped twice and nothing changes. This is the question, and it is easy to check by tracing a 2×2.
"How would you rotate anticlockwise?" Transpose, then reverse the columns.
"Can you do it in one pass?" The four-way layer rotation. Say it is harder to get right.
"What if the matrix were not square?" The rotation changes the dimensions, so it cannot be done in place — you allocate an n × m result.
One thing to volunteer: give the full recipe table. It costs one sentence and covers every variation an interviewer might ask for.
Next:4.28.2 Spiral Matrix — where the difficulty is entirely in the boundary conditions.