48. Rotate Image (Medium)

Problem

Rotate an n × n 2D matrix representing an image 90° clockwise. Do it in place, don’t allocate another matrix.

Example

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

LeetCode 48 · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Allocate a new matrix

new[j][n - 1 - i] = old[i][j]. Not in-place, but clarifies the coordinate transform.

Python

def rotate(matrix):
    n = len(matrix)                             # L1: O(1)
    new = [[0] * n for _ in range(n)]           # L2: O(n²)
    for i in range(n):                          # L3: outer loop, n iterations
        for j in range(n):                      # L4: inner loop, n iterations
            new[j][n - 1 - i] = matrix[i][j]   # L5: O(1) coordinate remap
    for i in range(n):
        matrix[i] = new[i]                      # L6: O(n) per row copy

TypeScript

function rotate(matrix: number[][]): void {
    const n = matrix.length;                             // L1: O(1)
    const neu: number[][] = Array.from({ length: n }, () => new Array(n).fill(0)); // L2: O(n²)
    for (let i = 0; i < n; i++) {                        // L3: outer loop, n iterations
        for (let j = 0; j < n; j++) {                    // L4: inner loop, n iterations
            neu[j][n - 1 - i] = matrix[i][j];           // L5: O(1) coordinate remap
        }
    }
    for (let i = 0; i < n; i++) matrix[i] = neu[i];     // L6: O(n) per row copy
}

Go

func rotate(matrix [][]int) {
    n := len(matrix)                                      // L1: O(1)
    neu := make([][]int, n)
    for i := range neu { neu[i] = make([]int, n) }        // L2: O(n²)
    for i := 0; i < n; i++ {                              // L3: outer loop, n iterations
        for j := 0; j < n; j++ {                          // L4: inner loop, n iterations
            neu[j][n-1-i] = matrix[i][j]                  // L5: O(1) coordinate remap
        }
    }
    for i := 0; i < n; i++ { matrix[i] = neu[i] }         // L6: O(n) per row copy
}

Swift

final class Solution {
    func rotate(_ matrix: inout [[Int]]) {
        let size = matrix.count
        guard size > 0 else { return }
        var rotated = Array(repeating: Array(repeating: 0, count: size), count: size)
        for row in 0..<size {
            for column in 0..<size {
                rotated[column][size - 1 - row] = matrix[row][column]
            }
        }
        matrix = rotated
    }
}

Where the time goes, line by line

Variables: n = matrix side length (n×n).

Line	Per-call cost	Times executed	Contribution
L2 (alloc new matrix)	$O(1)$	n²	$O(n²)$
L3, L4, L5 (remap loop)	$O(1)$	n²	$O(n²)$ ← dominates
L6 (copy rows back)	$O(n)$	n	$O(n²)$

Every cell is visited once for the remap and once for the copy-back.

Complexity

• Time: $O(n²)$, driven by L3/L4/L5 (the cell-by-cell remap).
• Space: $O(n²)$ for the auxiliary matrix.

Violates the in-place constraint.

Approach 2: Rotate four cells at a time (in-place)

Rotate the outermost ring, then the next inner ring, etc. Each rotation is a four-cell swap.

Python

def rotate(matrix):
    n = len(matrix)                                 # L1: O(1)
    for r in range(n // 2):                         # L2: n/2 rings
        for c in range(r, n - r):                   # L3: n-2r cells per ring
            tmp = matrix[r][c]                      # L4: save top-left
            matrix[r][c] = matrix[n - 1 - c][r]    # L5: left -> top
            matrix[n - 1 - c][r] = matrix[n - 1 - r][n - 1 - c]  # L6: bottom -> left
            matrix[n - 1 - r][n - 1 - c] = matrix[c][n - 1 - r]  # L7: right -> bottom
            matrix[c][n - 1 - r] = tmp              # L8: top -> right

TypeScript

function rotate(matrix: number[][]): void {
    const n = matrix.length;                                     // L1: O(1)
    for (let r = 0; r < Math.floor(n / 2); r++) {              // L2: n/2 rings
        for (let c = r; c < n - r - 1; c++) {                  // L3: n-2r-1 cells per ring
            const tmp = matrix[r][c];                            // L4: save top-left
            matrix[r][c] = matrix[n - 1 - c][r];               // L5: left -> top
            matrix[n - 1 - c][r] = matrix[n - 1 - r][n - 1 - c]; // L6: bottom -> left
            matrix[n - 1 - r][n - 1 - c] = matrix[c][n - 1 - r]; // L7: right -> bottom
            matrix[c][n - 1 - r] = tmp;                         // L8: top -> right
        }
    }
}

Go

func rotate(matrix [][]int) {
    n := len(matrix)                                   // L1: O(1)
    for r := 0; r < n/2; r++ {                        // L2: n/2 rings
        for c := r; c < n-r-1; c++ {                  // L3: n-2r-1 cells per ring
            tmp := matrix[r][c]                        // L4: save top-left
            matrix[r][c] = matrix[n-1-c][r]           // L5: left -> top
            matrix[n-1-c][r] = matrix[n-1-r][n-1-c]  // L6: bottom -> left
            matrix[n-1-r][n-1-c] = matrix[c][n-1-r]  // L7: right -> bottom
            matrix[c][n-1-r] = tmp                    // L8: top -> right
        }
    }
}

Swift

final class Solution {
    func rotate(_ matrix: inout [[Int]]) {
        let size = matrix.count
        guard size > 1 else { return }
        for layer in 0..<(size / 2) {
            let last = size - 1 - layer
            for offset in 0..<(last - layer) {
                let top = matrix[layer][layer + offset]
                matrix[layer][layer + offset] = matrix[last - offset][layer]
                matrix[last - offset][layer] = matrix[last][last - offset]
                matrix[last][last - offset] = matrix[layer + offset][last]
                matrix[layer + offset][last] = top
            }
        }
    }
}

Where the time goes, line by line

Variables: n = matrix side length (n×n).

Line	Per-call cost	Times executed	Contribution
L2 (ring loop)	$O(1)$	n/2	$O(n)$
L3-L8 (four-cell swap)	$O(1)$	n²/4 total cells	$O(n²)$ ← dominates

Each of the n²/4 non-center cells is visited once in the four-cell swap; the four assignments per cell are all $O(1)$.

Complexity

• Time: $O(n²)$, driven by L3/L4-L8 (visiting every cell in every ring).
• Space: $O(1)$.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Transpose + reverse each row (canonical)

90° clockwise rotation = transpose + reverse each row.

Python

def rotate(matrix):
    n = len(matrix)
    # Transpose
    for i in range(n):                              # L1: outer loop, n iterations
        for j in range(i + 1, n):                   # L2: upper-triangle only
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]  # L3: O(1) swap
    # Reverse each row
    for row in matrix:                              # L4: n rows
        row.reverse()                               # L5: O(n) per row

TypeScript

function rotate(matrix: number[][]): void {
    const n = matrix.length;
    // Transpose
    for (let i = 0; i < n; i++) {                           // L1: outer loop, n iterations
        for (let j = i + 1; j < n; j++) {                   // L2: upper-triangle only
            [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];  // L3: O(1) swap
        }
    }
    // Reverse each row
    for (const row of matrix) {                             // L4: n rows
        row.reverse();                                      // L5: O(n) per row
    }
}

Go

func rotate(matrix [][]int) {
    n := len(matrix)
    // Transpose
    for i := 0; i < n; i++ {                              // L1: outer loop, n iterations
        for j := i + 1; j < n; j++ {                      // L2: upper-triangle only
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]  // L3: O(1) swap
        }
    }
    // Reverse each row
    for _, row := range matrix {                           // L4: n rows
        for lo, hi := 0, len(row)-1; lo < hi; lo, hi = lo+1, hi-1 {
            row[lo], row[hi] = row[hi], row[lo]            // L5: O(n) per row
        }
    }
}

Swift

final class Solution {
    func rotate(_ matrix: inout [[Int]]) {
        let size = matrix.count
        guard size > 1 else { return }
        for row in 0..<size {
            for column in (row + 1)..<size {
                let value = matrix[row][column]
                matrix[row][column] = matrix[column][row]
                matrix[column][row] = value
            }
        }
        for row in matrix.indices {
            matrix[row].reverse()
        }
    }
}

Where the time goes, line by line

Variables: n = matrix side length (n×n).

Line	Per-call cost	Times executed	Contribution
L1, L2, L3 (transpose)	$O(1)$	n(n-1)/2	$O(n²)$ ← dominates
L4, L5 (row reversal)	$O(n)$	n	$O(n²)$

Both the transpose and the row-reversal pass touch every cell once.

Complexity

• Time: $O(n²)$, driven by L1/L2/L3 (transpose) and L4/L5 (row reversal), both $O(n²)$.
• Space: $O(1)$.

Shortest and easiest to remember. Counter-clockwise = transpose + reverse each column (or reverse rows first, then transpose).

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
New matrix	$O(n²)$	$O(n²)$
Four-cell in-place rotation	$O(n²)$	$O(1)$
Transpose + row reverse	$O(n²)$	$O(1)$

Test cases

Python

# Quick smoke tests, paste into a REPL or save as test_048.py and run.
# Uses the canonical implementation (Approach 3: transpose + row reverse).
# rotate() modifies the matrix in place.

def rotate(matrix):
    n = len(matrix)
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    for row in matrix:
        row.reverse()

def _run_tests():
    m = [[1,2,3],[4,5,6],[7,8,9]]
    rotate(m)
    assert m == [[7,4,1],[8,5,2],[9,6,3]]

    m2 = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
    rotate(m2)
    assert m2 == [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

    m3 = [[1]]  # 1x1 edge case
    rotate(m3)
    assert m3 == [[1]]

    m4 = [[1,2],[3,4]]
    rotate(m4)
    assert m4 == [[3,1],[4,2]]

    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function rotate(matrix: number[][]): void {
    const n = matrix.length;
    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]];
    for (const row of matrix) row.reverse();
}

const m = [[1,2,3],[4,5,6],[7,8,9]];
rotate(m);
console.assert(JSON.stringify(m) === JSON.stringify([[7,4,1],[8,5,2],[9,6,3]]));
const m2 = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]];
rotate(m2);
console.assert(JSON.stringify(m2) === JSON.stringify([[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]));
const m3 = [[1]];
rotate(m3);
console.assert(JSON.stringify(m3) === JSON.stringify([[1]]));
const m4 = [[1,2],[3,4]];
rotate(m4);
console.assert(JSON.stringify(m4) === JSON.stringify([[3,1],[4,2]]));
console.log('all tests pass');

Related data structures

• Arrays, 2D matrix in-place transforms

Related concepts

• Simulation, the explicit state model for executing rules exactly while keeping cases organized.
• Array Scans, the linear pass habit of carrying just enough state while reading each item once.