4.28.1 — Rotate Image

LeetCode 48 · Medium

The problem

Rotate an n × n matrix 90 degrees clockwise, in place.

1 2 3        7 4 1
4 5 6   →    8 5 2
7 8 9        9 6 3

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 9

Reverse each row.

1 4 7        7 4 1
2 5 8   →    8 5 2
3 6 9        9 6 3

Done. 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()

TypeScript

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();
}

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.

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:

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.

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.