48. Rotate Image

The trap in Rotate Image is the “in-place” clause — anyone can rotate a matrix into a fresh copy, but the interviewer wants it done with no second grid. The clean trick is to stop thinking about rotation and decompose it into two moves you already know. It’s a staple of the matrix and geometry pattern, where the win is almost always finding the right index relationship.

The problem

You’re given an n x n matrix that represents an image, and you have to rotate it 90° clockwise — the top row becomes the right column, and so on — while modifying the matrix directly instead of returning a new one. (Full statement on LeetCode.)

A 3×3 makes the target concrete:

1 2 3        7 4 1
4 5 6   -->  8 5 2
7 8 9        9 6 3

The first row 1 2 3 ends up as the last column, read top to bottom.

Intuition: a clockwise turn is a transpose plus a flip

Work out where element (r, c) lands after a 90° clockwise turn. In an n x n grid it moves to (c, n-1-r): the old row index becomes the new column, and the old column becomes the new row counted from the top. Doing that directly means juggling four cells at once, which is fiddly to get right under pressure.

There’s a cleaner path. Split the transform into two familiar ones:

$\underbrace{(r, c) \to (c, r)}_{\text{transpose}} \;\to\; \underbrace{(c, r) \to (c, n-1-r)}_{\text{reverse each row}}$

First transpose — mirror across the main diagonal, swapping matrix[i][j] with matrix[j][i]. That flips the grid but leaves it mirror-imaged. Then reverse each row, which undoes the mirror and leaves exactly the clockwise rotation. Compose the two mappings and you land back at $(r, c) \to (c, n-1-r)$, so it’s provably the right turn, not a lucky coincidence.

Solution

The one detail that matters in the transpose loop: start the inner index at j = i + 1. Iterating over the full grid would swap every pair twice and hand you back the original matrix.

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;

        // Step 1: transpose across the main diagonal.
        // j starts at i+1 so each pair is swapped exactly once.
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = tmp;
            }
        }

        // Step 2: reverse each row to turn the mirror into a rotation.
        for (int[] row : matrix) {
            int left = 0, right = n - 1;
            while (left < right) {
                int tmp = row[left];
                row[left] = row[right];
                row[right] = tmp;
                left++;
                right--;
            }
        }
    }
}

Both passes only ever swap existing cells, so no extra matrix is allocated — the “in-place” requirement is satisfied by construction.

Complexity

	Time	Space
Transpose + reverse	$O(n^2)$	$O(1)$

You touch every one of the $n^2$ cells a constant number of times, and the only extra memory is a single swap temporary.

In an interview

Say the decomposition out loud before writing anything: “a clockwise rotation is a transpose followed by reversing each row.” That one line shows you found the structure instead of hacking at indices. Then flag the two bugs interviewers wait for — running the transpose over the whole grid (which cancels itself out) and reversing columns instead of rows (that gives a counter-clockwise turn).

If they push for the alternative, mention the layer-by-layer version that rotates four cells in one cycle from the outer ring inward; it’s the same $O(1)$ space but far easier to fumble, which is exactly why transpose-plus-reverse is the answer to reach for. The same “figure out where each index maps” muscle drives Spiral Matrix and Set Matrix Zeroes, and the matrix and geometry hub collects the rest.

References

• LeetCode 48 — Rotate Image