Appearance
4.28.1 — Rotate Image
LeetCode 48 · Medium
The problem
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:
nis up to 20, which is very small, but you must do it in place (using O(1) extra memory). - Edge cases:
n = 1is an immediate return. Elements can be negative.
1 2 3 7 4 1
4 5 6 → 8 5 2
7 8 9 9 6 3Brute Force Approach
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.
The pattern
Working out the index arithmetic for a rotation directly is error-prone. There is a much easier route:
Transpose, then reverse each row.
Transpose flips the matrix over its main diagonal — swap matrix[i][j] with matrix[j][i].
1 2 3 1 4 7
4 5 6 → 2 5 8
7 8 9 3 6 9Reverse each row.
1 4 7 7 4 1
2 5 8 → 8 5 2
3 6 9 9 6 3Done. Two simple operations, each obviously correct, replacing one formula that is easy to get wrong.
Why it works
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.
The solution
python
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):
for j in range(i + 1, n): # j starts at i+1
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# 2. reverse each row
for row in matrix:
row.reverse()ts
function rotate(matrix: number[][]): void {
const n = matrix.length;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
[matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
}
}
for (const row of matrix) row.reverse();
}Code Walkthrough:
- Step 1 (Transpose): We loop over the rows with index
i. For each rowi, we loopjfromi + 1ton - 1. We swapmatrix[i][j]withmatrix[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.
Complexity
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
jfromi+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.
The layer-by-layer alternative
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] = topSame 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.
Where this goes next
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.
What the interviewer will push on
"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.