LeetCode #48 — Medium

Rotate Image

Rotate an n x n matrix 90 degrees clockwise in-place — decomposed into two elegant operations.

The Problem

Problem Statement

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

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

Example 2:

Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

Constraints:

n == matrix.length == matrix[i].length
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000

Step 01

Brute Force — Extra Matrix

The simplest approach: create a new matrix, and for each element at (i, j), place it at (j, n-1-i) in the new matrix.

Mapping Rule: (i, j) maps to (j, n-1-i)

ORIGINAL

            (0,0)=1  (0,1)=2  (0,2)=3

            (1,0)=4  (1,1)=5  (1,2)=6

            (2,0)=7  (2,1)=8  (2,2)=9

ROTATED

            (0,0)=7  (0,1)=4  (0,2)=1

            (1,0)=8  (1,1)=5  (1,2)=2

            (2,0)=9  (2,1)=6  (2,2)=3

This works but uses O(n^2) extra space. The problem requires in-place rotation — can we do it without a second matrix?

💡

Key observation: A 90-degree clockwise rotation can be decomposed into two simpler operations that are each easy to do in-place: transpose then reverse each row.

Step 02

The Core Insight — Transpose + Reverse

A 90-degree clockwise rotation equals: transpose the matrix (swap rows and columns), then reverse each row.

The Two-Step Formula

Step A: Transpose

Swap matrix[i][j] with matrix[j][i] for all j > i. This mirrors across the main diagonal.

Step B: Reverse Rows

For each row, swap elements from both ends moving inward. This mirrors across the vertical center.

⚡

Why does this work? Transposing maps (i,j) to (j,i). Reversing rows then maps (j,i) to (j, n-1-i). The combined effect: (i,j) goes to (j, n-1-i) — which is exactly the 90-degree clockwise rotation formula.

Other Rotation Directions

90 CW: Transpose + Reverse rows

90 CCW: Reverse rows + Transpose (or Transpose + Reverse columns)

180: Reverse rows + Reverse columns

Step 03

Walkthrough with 3x3 Grid

Let's watch the transformation step by step on [[1,2,3],[4,5,6],[7,8,9]].

Original Matrix

Rows are color-coded: row 0, row 1, row 2

↓

Step A: Transpose (mirror across diagonal)

Before

→

After Transpose

Elements above the diagonal (highlighted in red) swap with their mirror below. Diagonal elements (1, 5, 9) stay in place. Swaps: (0,1)↔(1,0), (0,2)↔(2,0), (1,2)↔(2,1).

↓

Step B: Reverse Each Row

After Transpose

→

Final (Rotated 90 CW)

Each row's first and last elements swap. Middle elements (in odd-sized rows) stay in place. Result: [[7,4,1],[8,5,2],[9,6,3]].

Step 04

Edge Cases

1x1 matrix: [[5]]

Nothing to do. A single element is already "rotated." Both loops execute zero iterations.

2x2 matrix: [[1,2],[3,4]]

Transpose swaps (0,1)↔(1,0): [[1,3],[2,4]]. Reverse rows: [[3,1],[4,2]]. Just 2 swap operations total.

Even-sized (4x4)

Works identically. Transpose swaps 6 pairs above diagonal. Each row reverse swaps 2 pairs. No special handling needed for even vs odd.

Odd-sized (5x5)

Center element (2,2) stays in place during both transpose and reverse. All other elements participate in swaps normally.

Step 05

Full Annotated Code

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

        // Step 1: Transpose — mirror across main diagonal
        // Only iterate upper triangle (j starts at i+1)
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];      // swap (i,j) with (j,i)
                matrix[j][i] = temp;
            }

        // Step 2: Reverse each row
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n / 2; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][n - 1 - j]; // swap left with right
                matrix[i][n - 1 - j] = temp;
            }
    }
}

func rotate(matrix [][]int) {
    n := len(matrix)

    // Step 1: Transpose — mirror across main diagonal
    // Only iterate upper triangle (j starts at i+1)
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] // swap (i,j) with (j,i)
        }
    }

    // Step 2: Reverse each row
    for i := 0; i < n; i++ {
        for j := 0; j < n/2; j++ {
            matrix[i][j], matrix[i][n-1-j] = matrix[i][n-1-j], matrix[i][j] // swap left with right
        }
    }
}

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

    # Step 1: Transpose — mirror across main diagonal
    # Only iterate upper triangle (j starts at i+1)
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]  # swap (i,j) with (j,i)

    # Step 2: Reverse each row
    for i in range(n):
        matrix[i].reverse()

impl Solution {
    pub fn rotate(matrix: &mut Vec<Vec<i32>>) {
        let n = matrix.len();

        // Step 1: Transpose — mirror across main diagonal
        // Only iterate upper triangle (j starts at i+1)
        for i in 0..n {
            for j in (i+1)..n {
                let tmp = matrix[i][j];
                matrix[i][j] = matrix[j][i]; // swap (i,j) with (j,i)
                matrix[j][i] = tmp;
            }
        }

        // Step 2: Reverse each row
        for i in 0..n {
            matrix[i].reverse(); // swap left with right
        }
    }
}

function rotate(matrix: number[][]): void {
    const n = matrix.length;

    // Step 1: Transpose — mirror across main diagonal
    // Only iterate 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]]; // swap (i,j) with (j,i)

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

Step 06

Interactive Demo

Choose a matrix size and step through the transpose and reverse operations. Watch the cells swap positions in real-time.

Rotation Visualizer

Matrix Size

Step 07

Complexity Analysis

Time

O(n²)

Space

O(1)

We visit each element a constant number of times: once during transpose, once during row reversal. That is O(n²) total operations for an n × n matrix. No extra data structures -- just a single temp variable for swapping.

Approach Breakdown

BRUTE FORCE

O(n2) time

O(n2) space

Allocate a second n × n matrix and copy each element from (i, j) to (j, n-1-i). Two nested loops visit all n² cells once. The extra matrix doubles memory usage, which the problem explicitly disallows.

OPTIMAL

O(n2) time

O(1) space

Transpose swaps n(n-1)/2 pairs above the diagonal; reversing each row swaps n/2 pairs per row. Both passes touch every element a constant number of times for O(n²) total. Only a single temp variable is needed -- no extra matrix.

🎯

"Transpose then reverse" is an algebraic decomposition of 90-degree rotation -- each element moves exactly once per step. Any rotation must move O(n²) elements, so the time is optimal. The O(1) space is strictly better than allocating a second matrix.

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Off-by-one on range boundaries

Wrong move: Loop endpoints miss first/last candidate.

Usually fails on: Fails on minimal arrays and exact-boundary answers.

Fix: Re-derive loops from inclusive/exclusive ranges before coding.

Overflow in intermediate arithmetic

Wrong move: Temporary multiplications exceed integer bounds.

Usually fails on: Large inputs wrap around unexpectedly.

Fix: Use wider types, modular arithmetic, or rearranged operations.