Rotate Image

Rotate Image is the most-asked matrix problem. The version with a second matrix takes two minutes. The in-place version is the real question, and it has two good answers: a neat identity (transpose then reverse), and a direct four-way swap around each ring. Knowing both, and knowing why the identity works, is what interviewers look for.

The problem

You get an n × n matrix of integers. Rotate it 90 degrees clockwise. You must change the matrix in place — do not create a second matrix and return it.

Example 1.

input           output1 2 3           7 4 14 5 6    →      8 5 27 8 9           9 6 3

The top row 1 2 3 becomes the right column, read top to bottom.

Example 2. [[5, 1, 9, 11], [2, 4, 8, 10], [13, 3, 6, 7], [15, 14, 12, 16]] → [[15, 13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7, 10, 11]].

Constraints. 1 ≤ n ≤ 20, and the matrix is always square.

Clarifying questions

• Always square? Yes. A non-square matrix cannot be rotated in place, since its shape changes.
• Clockwise? Yes. (Anticlockwise is a common follow-up.)
• Truly O(1) extra space? Yes — a few variables, no copy.
• Values? Any integers; they do not affect the method.

Approach 1: the simple way

Work out where each cell goes, and write it into a new matrix. In a clockwise rotation, row r becomes column n − 1 − r, and column c becomes row c. So matrix[r][c] moves to result[c][n - 1 - r].

1def rotate_copy(matrix: list[list[int]]) -> None:2    """Brute force: build the rotated matrix, then copy it back."""3    n = len(matrix)4    result = [[0] * n for _ in range(n)]5    for r in range(n):6        for c in range(n):7            result[c][n - 1 - r] = matrix[r][c]8    matrix[:] = result

Check it on the 1: it is at (0, 0) and goes to (0, 2), the top-right corner. Correct.

This is O(n²) time, which is optimal — every cell must move. But it uses O(n²) extra space for result, and the problem requires in place. Writing directly into matrix instead would overwrite values before they are moved: the 1 would land on the 3 before the 3 had been read.

The key insight

A rotation is hard to do in place, but reflections are easy — a reflection just swaps pairs of cells, and a swap never loses anything.

Two reflections in a row make a rotation. Reflect across the main diagonal (the transpose: swap matrix[r][c] with matrix[c][r]), then reflect left-to-right (reverse each row). Geometry says two reflections across lines that meet at an angle θ make a rotation by 2θ. The diagonal and the vertical centre line meet at 45 degrees, so the result is a 90-degree rotation.

You do not need the geometry to trust it. Check it on the example: transposing 1 2 3 / 4 5 6 / 7 8 9 gives 1 4 7 / 2 5 8 / 3 6 9, and reversing each row gives 7 4 1 / 8 5 2 / 9 6 3. That is the answer.

Approach 2: transpose, then reverse each row

1def rotate(matrix: list[list[int]]) -> None:2    """Rotate 90 degrees clockwise in place: transpose, then reverse each row."""3    n = len(matrix)4    for r in range(n):5        for c in range(r + 1, n):            # upper triangle only: each pair swaps once6            matrix[r][c], matrix[c][r] = matrix[c][r], matrix[r][c]7    for row in matrix:8        row.reverse()

Step by step:

1. Transpose. Visit only cells above the diagonal (c from r + 1) and swap each with its mirror below. Diagonal cells stay put.
2. Reverse each row. row.reverse() works in place.

Dry run on the 3 × 3 example:

Three swaps for a 3 × 3 — one per pair above the diagonal, n(n − 1)/2 in general.

Complexity. O(n²) time: the transpose touches half the cells and the reversal touches all of them, each once. O(1) extra space.

Approach 3: rotate ring by ring

The identity is elegant, but it moves every cell twice. The direct way moves each cell once. Treat the matrix as rings (layers), from the outside in. In each ring, cells move in groups of four: top → right → bottom → left → top. Save one, then shift the other three along.

1def rotate_layers(matrix: list[list[int]]) -> None:2    """Rotate in place by cycling groups of four cells, one ring at a time."""3    n = len(matrix)4    for layer in range(n // 2):5        first, last = layer, n - 1 - layer6        for i in range(first, last):7            offset = i - first8            top = matrix[first][i]                                     # save top9            matrix[first][i] = matrix[last - offset][first]            # left   -> top10            matrix[last - offset][first] = matrix[last][last - offset] # bottom -> left11            matrix[last][last - offset] = matrix[i][last]              # right  -> bottom12            matrix[i][last] = top                                      # top    -> right

On the 3 × 3 there is one ring, with two groups. First the corners: 1 is saved, 7 moves to the top-left, 9 to the bottom-left, 3 to the bottom-right, and 1 to the top-right. Then the edge centres: 4 to the top, 8 to the left, 6 to the bottom, 2 to the right. Same result, 7 4 1 / 8 5 2 / 9 6 3.

Same O(n²) time and O(1) space, with each cell written once. It is harder to get right under pressure — four index expressions, each easy to mistype. Present the transpose version first and offer this as the "one pass" alternative.

All three approaches gave identical results on 300 random matrices from 0 × 0 to 8 × 8.

Edge cases

• 1 × 1. The transpose loop does nothing and reversing a one-item row does nothing. Correct.
• 2 × 2. One swap, then two reversals: [[1, 2], [3, 4]] becomes [[3, 1], [4, 2]].
• Even vs odd n. For odd n the centre cell never moves; for even n there is no centre. Both approaches handle this without a special case (range(n // 2) rings).

Follow-ups

• "Rotate anticlockwise." Transpose, then reverse the order of the rows (matrix.reverse()) instead of reversing within each row. Or reverse each row first and then transpose. (The old version of this course said "reverse the row order, then transpose" — that produces a clockwise rotation. Checked in code, it returned 7 4 1 / 8 5 2 / 9 6 3.)
• "Rotate 180 degrees." Reverse the order of the rows, then reverse each row. No transpose needed.
• "The matrix is m × n, not square." In-place is impossible, since the shape becomes n × m. Build a new matrix with result[c][m - 1 - r] = matrix[r][c], or in Python [list(row) for row in zip(*matrix[::-1])].