Chapter 048

Rotate Image

An n × n matrix, in place.

medium·12 min read·array, math, matrix·asked at Amazon·Microsoft

Given a square n × n matrix of integers, rotate it by 90 degrees clockwise. You must rotate it in place — no allocating a second matrix1"In place" means O(1) extra space. You can use a handful of loop variables, but not a copy of the grid.. The whole game is: figure out where each cell moves, and do the shuffle without losing values.

Two worked examples

Example 1

Input matrix = [[1,2],[3,4]]

Output [[3,1],[4,2]]

The first column (3, 1) becomes the first row. The second column (4, 2) becomes the second row.

Example 2

Input matrix = [[1,2,3],[4,5,6],[7,8,9]]

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

Column 0 becomes row 0, column 1 becomes row 1, and so on. Read the input bottom-up column by column to see the pattern.

Constraints

n == matrix.length == matrix[i].length
1 ≤ n ≤ 20
−1000 ≤ matrix[i][j] ≤ 1000

Prerequisites

2D indexing — accessing matrix[i][j] without confusing rows and columns.
Matrix transpose — swapping across the main diagonal, where (i, j) trades places with (j, i).
In-place manipulation — mutating a structure without a second copy.
Layer-by-layer processing — walking outer boundaries inward, four cells at a time.

§Approach 01 · Brute Force

The obvious path.

The straightforward move is to allocate a fresh n × n matrix and drop each element where it belongs. The key observation for a 90° clockwise rotation: the element at (i, j) ends up at (j, n − 1 − i).2Derivation: after transpose, (i, j) → (j, i). After a horizontal flip, (j, i) → (j, n − 1 − i). Two moves collapse to one formula.

Algorithm

Allocate a new n × n matrix called rotated.
For every matrix[i][j], set rotated[j][n − 1 − i] = matrix[i][j].
Copy rotated back into matrix, row by row.

brute_force.py

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        rotated = [[0] * n for _ in range(n)]

        for i in range(n):
            for j in range(n):
                rotated[j][n - 1 - i] = matrix[i][j]

        for i in range(n):
            for j in range(n):
                matrix[i][j] = rotated[i][j]

BruteForce.java

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

        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                rotated[j][n - 1 - i] = matrix[i][j];

        for (int i = 0; i < n; i++)
            matrix[i] = rotated[i];
    }
}

TimeO(n²)

SpaceO(n²)

It passes. It also violates the point of the question — in place. Onward.

§Approach 02 · Layer by Layer

Four cells at a time.

Instead of moving each cell into a fresh matrix, rotate the ring in place. For each outer layer, elements move in four-cell cycles:

top-left → top-right
top-right → bottom-right
bottom-right → bottom-left
bottom-left → top-left

Save the top-left in a temp variable3One first variable per cycle. That is your entire O(1) overhead., then move each of the other three around clockwise. Repeat for every position along the ring, then shrink to the next inner ring.

Algorithm

Set l = 0, r = n − 1 as the current layer's bounds.
While l < r, for each offset i from 0 to r − l − 1:
Save first = matrix[l][l + i] — the top-left of this cycle.
matrix[l][l + i] = matrix[r − i][l] — bottom-left rides up.
matrix[r − i][l] = matrix[r][r − i] — bottom-right slides left.
matrix[r][r − i] = matrix[l + i][r] — top-right drops down.
matrix[l + i][r] = first — saved top-left lands at top-right.
After each ring, l += 1, r -= 1. Continue inward.

READY—

Press ▶ or step forward to begin.

✓

—

matrix (JSON)

Space Play/Pause·←→ Step·R Reset·F Fullscreen

Executing Code

def rotate(self, matrix: List[List[int]]) -> None:

    l = 0

    r = (len(matrix)) - 1

    while l < r:

        for i in range(r - l):

            top = l; bottom = r

            first = matrix[top][l + i]

            matrix[top][l + i] = matrix[bottom - i][l]

            matrix[bottom - i][l] = matrix[bottom][r - i]

            matrix[bottom][r - i] = matrix[top + i][r]

            matrix[top + i][r] = first

        l += 1

        r -= 1

    return matrix

Fig. 1. Watch the four-cell cycle rotate around each concentric ring. The temp variable first is the entire memory budget. Toggle fullscreen with F.

TimeO(n²)

SpaceO(1)

§Approach 03 · Optimal

Reverse, then transpose.

The four-cell dance works but is fiddly. There is a two-line rewrite that produces the same result and reads like English:

Reverse the rows vertically. Swap row 0 with row n − 1, row 1 with row n − 2, and so on. Element at (i, j) moves to (n − 1 − i, j).
Transpose across the main diagonal. For all i < j, swap matrix[i][j] with matrix[j][i]. Element at (n − 1 − i, j) moves to (j, n − 1 − i).

Two lines. Same destination as the four-cell rotation.4Order matters. Reverse rows then transpose gives clockwise. Transpose then reverse rows gives counter-clockwise. Pick one and stick with it.This is the version I would write in an interview: less code, less error surface, identical complexity.

READY—

Press ▶ or step forward to begin.

✓

—

matrix (JSON)

Space Play/Pause·←→ Step·R Reset·F Fullscreen

Executing Code

def rotate(self, matrix: List[List[int]]) -> None:

    # Step 1: reverse rows vertically

    matrix.reverse()

    # Step 2: transpose (swap across main diagonal)

    for i in range(len(matrix)):

        for j in range(i + 1, len(matrix)):

            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

Fig. 2. Two passes: rows flip vertically, then the upper triangle mirrors down. The final grid is the 90° clockwise rotation.

TimeO(n²)

SpaceO(1)

§Mistakes you'll make

Three ways this goes wrong.

Confusing clockwise with counter-clockwise.

For 90° clockwise: reverse rows, then transpose. For counter-clockwise: transpose, then reverse rows. Same two operations, opposite order. If you memorize one, memorize this: reverse-first is clockwise.

Transposing the whole matrix instead of the upper triangle.

When you transpose in place, the inner loop must start at j = i + 1. If you start at j = 0, every pair is swapped twice — the matrix ends up right back where it started. This is the mistake I see most often on a whiteboard.

pitfall.py

# Wrong: swaps every pair twice, returns original matrix
for i in range(n):
    for j in range(n):
        matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

# Correct: only upper triangle
for i in range(n):
    for j in range(i + 1, n):
        matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

Mixing up index arithmetic in the four-cell version.

In the layer-by-layer approach, blending up top, bottom, l, r, and the offset i produces cells that land in the wrong slot and quietly overwrite each other. The four assignments must follow the exact clockwise order: save top-left first, then bottom-left → top-left, bottom-right → bottom-left, top-right → bottom-right, saved value → top-right. If you cannot recite that in the interview, use the two-line reverse-then-transpose approach instead. It has fewer places to make this mistake.

Discussion

…

Loading comments…

LeetMotion

class Solution: def rotate(self, matrix: List[List[int]]) -> None: n = len(matrix) rotated = [[0] * n for _ in range(n)] for i in range(n): for j in range(n): rotated[j][n - 1 - i] = matrix[i][j] for i in range(n): for j in range(n): matrix[i][j] = rotated[i][j]

class Solution { public void rotate(int[][] matrix) { int n = matrix.length; int[][] rotated = new int[n][n]; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) rotated[j][n - 1 - i] = matrix[i][j]; for (int i = 0; i < n; i++) matrix[i] = rotated[i]; } }

# Wrong: swaps every pair twice, returns original matrix for i in range(n): for j in range(n): matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] # Correct: only upper triangle for i in range(n): for j in range(i + 1, n): matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]