Rotate Image 90° Clockwise — Transpose + Reverse, In-Place O(n²) [Amazon, Microsoft, Google]

Problem Statement

You are given an n × n 2D matrix representing an image. Rotate the image by 90 degrees clockwise — in-place, without allocating a second matrix.

Example:

Input:              Output:
1  2  3             7  4  1
4  5  6    --->     8  5  2
7  8  9             9  6  3

The top row [1, 2, 3] becomes the rightmost column; the left column [1, 4, 7] becomes the top row. Every pixel slides to its new position without ever using a scratch buffer.

• Why This Problem Matters
• The Mathematical Insight
• The Transpose + Reverse Approach
• Step 1 — Transpose the matrix
• Step 2 — Reverse each row
• Why does this equal a 90° clockwise rotation?
• The 4-Cell Direct Rotation Approach
• Counterclockwise Rotation
• Visual Dry Run
• Starting state
• Transpose — swap upper-triangle pairs
• Reverse each row
• Common Mistakes
• Solutions
• Python — Transpose + Reverse (Recommended)
• Python — 4-Cell Direct Rotation
• JavaScript — Transpose + Reverse (Recommended)
• JavaScript — 4-Cell Direct Rotation
• Complexity Analysis
• Follow-up Questions
• This Pattern Solves
• Key Takeaway

Why This Problem Matters

Rotate Image (LeetCode 48) is a staple of FAANG interviews — it has appeared in on-site rounds at Amazon, Microsoft, and Google, and belongs to the canonical "Blind 75" list that engineers use to prepare for top-tier technical interviews.

The reason companies keep reaching for it is not that rotating a matrix is a common production task. It is that the problem elegantly separates engineers who think procedurally from engineers who think geometrically. To solve it well you need to:

1. Reason spatially. You must picture where each element needs to land after rotation, not just shuffle values mechanically.
2. Work within a constraint. The in-place requirement rules out the naive "copy into new matrix" approach and forces you to think about cycle structures.
3. Compose simple operations. The best solution decomposes a complex transformation (rotation) into two trivial ones (transpose, reverse). This "simplify by decomposing" habit is exactly what seniors look for in candidates.
4. Generalise cleanly. Interviewers immediately follow up: "Now do counterclockwise", "Now do 180°", "Now trace a spiral". An engineer who understands why the algorithm works can adapt in seconds; one who memorised it cannot.

The problem also sits at the intersection of several interview topics — arrays, in-place mutation, index math, and two-pointer technique — making it an efficient signal for a broad range of skills.

The Mathematical Insight

Before writing a single line of code, understand where each element must go.

For a clockwise 90° rotation of an n × n matrix:

An element at position (i, j) moves to position (j, n-1-i).

Let us verify with our 3×3 example (n = 3, so n-1 = 2):

This is also the geometric rule for rotating a point (x, y) by 90° clockwise about the origin: (x, y) → (y, -x). In matrix-index space "negate and clamp to [0, n-1]" translates the -x to n-1-i.

Every algorithm for this problem is just a different strategy for executing this coordinate mapping in-place.

The Transpose + Reverse Approach

This is the preferred interview solution because it is composed of two operations that are simple to explain, simple to code, and simple to prove correct.

Step 1 — Transpose the matrix

Swap matrix[i][j] with matrix[j][i] for every cell in the upper triangle (where j > i).

Original:        After transpose:
1  2  3          1  4  7
4  5  6   --->   2  5  8
7  8  9          3  6  9

The transpose reflects the matrix across its main diagonal. Rows become columns.

Critical loop-bound detail: iterate j from i+1 (not from 0). If you start j at 0 you swap each pair twice, undoing the work. This is one of the most common bugs on this problem.

Step 2 — Reverse each row

After transpose:   After reversing rows:
1  4  7            7  4  1
2  5  8   --->     8  5  2
3  6  9            9  6  3

Why does this equal a 90° clockwise rotation?

Think about it compositionally:

• Transpose maps (i, j) → (j, i).
• Reverse each row of an n-column matrix maps (r, c) → (r, n-1-c).

Apply both in sequence to an original element at (i, j):

1. After transpose: position becomes (j, i).
2. After row-reverse: (j, i) → (j, n-1-i).

That is exactly the clockwise 90° mapping we derived above. The composition of two simple linear operations equals the rotation — that is the mathematical elegance that makes this trick famous.

The 4-Cell Direct Rotation Approach

Instead of composing operations, you can simulate the rotation directly by moving four cells at a time in a cycle.

Picture the outermost ring of the matrix. The corner at (0, 0) must land at (0, n-1), which must land at (n-1, n-1), which must land at (n-1, 0), which must land back at (0, 0). These four form one cycle. Do the same for every position along that ring, then shrink inward to the next ring.

For a 3×3 matrix, the outer ring has one non-trivial cycle per "layer step" (i=0, j from 0 to n-2-i):

Save top:    temp = matrix[top][left + j]
Left→Top:    matrix[top][left+j]          = matrix[bottom-j][left]
Bottom→Left: matrix[bottom-j][left]       = matrix[bottom][right-j]
Right→Bottom:matrix[bottom][right-j]      = matrix[top+j][right]
Top→Right:   matrix[top+j][right]         = temp

Where top, bottom, left, right are the boundaries of the current ring, and j indexes the position within that ring's side.

This approach is more mechanical and harder to explain under pressure, but it is a valid alternative when the interviewer explicitly forbids decomposing into two passes. Both approaches share identical asymptotic complexity.

Counterclockwise Rotation

To rotate 90° counterclockwise, reverse the order of the two operations:

1. Reverse each row first.
2. Then transpose (swap matrix[i][j] with matrix[j][i]).

Alternatively: transpose first, then reverse each column instead of each row.

Why? Because the counterclockwise mapping sends (i, j) → (n-1-j, i). Working backwards through the composition shows that reversing rows then transposing achieves exactly this.

For a 180° rotation, you can reverse every row and then reverse the order of the rows themselves (or equivalently, apply the 90° rotation twice).

Visual Dry Run

Let us trace [[1,2,3],[4,5,6],[7,8,9]] step by step through the transpose + reverse approach.

Starting state

┌───┬───┬───┐
│ 1 │ 2 │ 3 │  row 0
├───┼───┼───┤
│ 4 │ 5 │ 6 │  row 1
├───┼───┼───┤
│ 7 │ 8 │ 9 │  row 2
└───┴───┴───┘

Transpose — swap upper-triangle pairs

Pairs swapped (row, col notation):

• (0,1) ↔ (1,0): swap 2 and 4
• (0,2) ↔ (2,0): swap 3 and 7
• (1,2) ↔ (2,1): swap 6 and 8

┌───┬───┬───┐
│ 1 │ 4 │ 7 │  row 0
├───┼───┼───┤
│ 2 │ 5 │ 8 │  row 1
├───┼───┼───┤
│ 3 │ 6 │ 9 │  row 2
└───┴───┴───┘

Notice that each original row is now a column. Column 0 reads 1, 2, 3 from top to bottom — that was row 0.

Reverse each row

• [1, 4, 7] → [7, 4, 1]
• [2, 5, 8] → [8, 5, 2]
• [3, 6, 9] → [9, 6, 3]

┌───┬───┬───┐
│ 7 │ 4 │ 1 │  row 0
├───┼───┼───┤
│ 8 │ 5 │ 2 │  row 1
├───┼───┼───┤
│ 9 │ 6 │ 3 │  row 2
└───┴───┴───┘

This matches the expected output. Verify individual elements:

• 7 was at (2, 0), now at (0, 0) — destination (j, n-1-i) = (0, 2-2) = (0, 0). Correct.
• 3 was at (0, 2), now at (0, 2) — wait, (j, n-1-i) = (2, 2-0) = (2, 2). Check: 3 is at row 2, column 2 in the result. Correct.
• 1 was at (0, 0), now at (0, 2) — (j, n-1-i) = (0, 2-0) = (0, 2). Correct.

Common Mistakes

Four errors account for the majority of failed attempts on this problem:

1. Transposing the full square instead of only the upper triangle.

If you run for j in range(n) (instead of for j in range(i+1, n)), you swap each pair twice and end up with the original matrix unchanged. The transpose loop must visit each off-diagonal pair exactly once, which means restricting to j > i.

2. Confusing clockwise and counterclockwise.

Clockwise: transpose → reverse rows. Counterclockwise: reverse rows → transpose (or transpose → reverse columns).

Getting these backwards produces a valid rotation — just in the wrong direction. Under interview pressure, draw the 2×2 case [[1,2],[3,4]] on paper and verify before coding.

3. Allocating extra space.

Creating a copy of the matrix (rotated = [row[:] for row in matrix]) and filling it from the formula rotated[j][n-1-i] = matrix[i][j] works correctly but violates the problem's explicit in-place constraint. This will cost you points in an interview even if the logic is sound.

4. Off-by-one in the 4-cell approach.

When iterating j within a ring of the direct rotation approach, the range should be range(i, n - 1 - i). Using range(i, n - i) processes one cell too many and corrupts the corner twice. The number of elements per side of a ring shrinks by one for each nested layer.

Solutions

Python — Transpose + Reverse (Recommended)

class Solution:
    def rotate(self, matrix: list[list[int]]) -> None:
        """
        Rotate the n×n matrix 90° clockwise in-place.
        Do not return anything; modify matrix in-place instead.
        """
        n = len(matrix)

        # Step 1: Transpose — swap every (i, j) with (j, i) for j > i only.
        # Visiting both triangles would undo the swaps.
        for i in range(n):
            for j in range(i + 1, n):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

        # Step 2: Reverse each row — turns transposed columns into rotated rows.
        for row in matrix:
            row.reverse()

Python — 4-Cell Direct Rotation

class Solution:
    def rotate(self, matrix: list[list[int]]) -> None:
        n = len(matrix)

        # Process ring by ring from the outside in.
        # floor(n/2) rings need processing; the centre of an odd matrix is fixed.
        for i in range(n // 2):
            last = n - 1 - i  # index of the opposite edge for this ring

            for j in range(i, last):
                offset = j - i  # how far along this ring's side we are

                # Save the top element
                temp = matrix[i][j]

                # Left → Top
                matrix[i][j] = matrix[last - offset][i]

                # Bottom → Left
                matrix[last - offset][i] = matrix[last][last - offset]

                # Right → Bottom
                matrix[last][last - offset] = matrix[i + offset][last]

                # Saved top → Right
                matrix[i + offset][last] = temp

JavaScript — Transpose + Reverse (Recommended)

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var rotate = function(matrix) {
    const n = matrix.length;

    // Step 1: Transpose — only the upper triangle (j starts at i+1).
    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]];
        }
    }

    // Step 2: Reverse each row in-place.
    for (let i = 0; i < n; i++) {
        matrix[i].reverse();
    }
};

JavaScript — 4-Cell Direct Rotation

/**
 * @param {number[][]} matrix
 * @return {void}
 */
var rotate = function(matrix) {
    const n = matrix.length;

    for (let i = 0; i < Math.floor(n / 2); i++) {
        const last = n - 1 - i;

        for (let j = i; j < last; j++) {
            const offset = j - i;
            const temp = matrix[i][j];

            // Left → Top
            matrix[i][j] = matrix[last - offset][i];

            // Bottom → Left
            matrix[last - offset][i] = matrix[last][last - offset];

            // Right → Bottom
            matrix[last][last - offset] = matrix[i + offset][last];

            // Saved Top → Right
            matrix[i + offset][last] = temp;
        }
    }
};

Complexity Analysis

Both approaches are asymptotically optimal: you must read every element at least once to know its value, so O(n²) time is a lower bound.

For constant-factor performance, the 4-cell approach touches each element exactly once, while transpose + reverse touches each element roughly 1.5 times on average (some in the transpose pass, all in the reverse pass). In practice on modern hardware with cache locality, the difference is negligible for any matrix size that fits in RAM.

Follow-up Questions

Interviewers commonly extend this problem in these directions:

1. Rotate counterclockwise. Reverse each row first, then transpose. The target mapping is (i, j) → (n-1-j, i).

2. Rotate 180°. Either apply 90° clockwise twice, or reverse the entire matrix top-to-bottom (reverse the row order), then reverse each individual row.

3. Spiral Matrix (LC 54). Given an m × n matrix, return all elements in clockwise spiral order. The boundary-shrinking pattern (track top, bottom, left, right) is the same ring-layer thinking used in the 4-cell rotation approach.

4. Set Matrix Zeroes (LC 73). If a cell is zero, set its entire row and column to zero — in-place. The key trick is using the first row and first column as flag arrays instead of allocating extra space, the same O(1) space discipline enforced here.

5. Rotate an m × n rectangular matrix. A non-square matrix cannot be rotated in-place without changing dimensions. The output shape changes from m × n to n × m, so you must allocate a new matrix and apply the (i, j) → (j, m-1-i) mapping directly.

This Pattern Solves

The "decompose into transpose + axis-flip" insight applies broadly:

• Image processing operations — flip horizontal, flip vertical, and 90°/270° rotations are all combinations of transpose and axis-reversal.
• Matrix layer traversal — Spiral Matrix, rotating sub-matrices, and diagonal walks all use the same "process the outer ring, shrink inward" loop structure from the 4-cell approach.
• Coordinate transformations — Whenever you need to remap (row, col) indices under a symmetry (rotation, reflection), writing out the before/after coordinates for two or three elements and solving for the formula is the fastest path to the correct code.
• In-place constraints with cycles — Any problem that says "rearrange without extra memory" can often be solved by identifying cycles in the permutation and rotating elements within each cycle. The 4-cell approach is a special case of this general technique.

Key Takeaway

The Rotate Image problem teaches you to decompose a geometrically complex operation — rotating every pixel in a matrix — into two primitively simple ones: transposing across the diagonal and reversing each row. Understanding why these compose to a 90° clockwise rotation (because (i,j) → (j,i) → (j, n-1-i)) is more valuable than memorising the two lines of code, because that understanding immediately tells you how to handle counterclockwise, 180°, and rectangular variants without re-deriving anything from scratch.