Skip to content

166 — Rotate Image

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 4 revisions

166 — Rotate Image

LeetCode 48 · Medium. You're given an n x n 2D matrix representing an image. Rotate the image by 90 degrees clockwise, in place — you must modify the matrix directly instead of allocating a new one.

🍽️ Intuition

Picture a square photograph lying flat on a table, and someone asks you to turn it 90 degrees clockwise without ever lifting it off the table or grabbing a second sheet of paper to copy it onto. You can't just "rotate" the physical paper here — the matrix's cells are fixed in memory. What you can do is push pixels around using clean, predictable moves. It turns out two simple moves compose into a perfect rotation: first, flip the image across its main diagonal (top-left to bottom-right) — this is a transpose, swapping row/column roles. Then, mirror each row left-to-right. Do both, and the photo lands exactly where a 90-degree clockwise turn would put it — no second photo needed.

Original:              Transpose (flip across        Reverse each row
                        the main diagonal):           (mirror left-right):

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

(this is the original matrix rotated 90° clockwise)

🚩 Pattern-Recognition Cue

"Rotate the matrix in place" — explicitly forbidding a second matrix — is the signal to decompose the rotation into cheap geometric building blocks (transpose + reflect, or a four-way cell swap walking inward layer by layer) rather than simulating the rotation cell-by-cell into fresh storage. Any time a 2-D grid problem insists on O(1) extra space, look for a way to express the transformation as a sequence of in-place swaps.

🐢 Brute Force

Compute where every cell should end up in a brand-new matrix using the rotation formula, then copy it back over the original.

func rotateBruteForce(_ matrix: inout [[Int]]) {
    let n = matrix.count
    var rotated = Array(repeating: Array(repeating: 0, count: n), count: n)

    for i in 0..<n {
        for j in 0..<n {
            // the cell at (i, j) moves to (j, n - 1 - i) under a 90° clockwise rotation
            rotated[j][n - 1 - i] = matrix[i][j]
        }
    }

    matrix = rotated
}

// smoke test
var image1: [[Int]] = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
rotateBruteForce(&image1)
print(image1)
// [[7, 4, 1], [8, 5, 2], [9, 6, 3]]

var image2: [[Int]] = [
    [5, 1, 9, 11],
    [2, 4, 8, 10],
    [13, 3, 6, 7],
    [15, 14, 12, 16]
]
rotateBruteForce(&image2)
print(image2)
// [[15, 13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7, 10, 11]]

Big-O: O(n²) time — every cell is visited once. O(n²) extra space for the temporary matrix, which is exactly what the problem forbids.

🚀 Optimal

Transpose the matrix in place (swap matrix[i][j] with matrix[j][i] for every j > i, so each pair is only swapped once), then reverse each row in place.

func rotate(_ matrix: inout [[Int]]) {
    let n = matrix.count

    // transpose: flip across the main diagonal
    for i in 0..<n {
        for j in (i + 1)..<n {
            let temp = matrix[i][j]
            matrix[i][j] = matrix[j][i]
            matrix[j][i] = temp
        }
    }

    // mirror each row left-to-right
    for i in 0..<n {
        matrix[i].reverse()
    }
}

// smoke test — same cases as the brute force
var image3: [[Int]] = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
rotate(&image3)
print(image3)
// [[7, 4, 1], [8, 5, 2], [9, 6, 3]]

var image4: [[Int]] = [
    [5, 1, 9, 11],
    [2, 4, 8, 10],
    [13, 3, 6, 7],
    [15, 14, 12, 16]
]
rotate(&image4)
print(image4)
// [[15, 13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7, 10, 11]]

Big-O: O(n²) time — the transpose visits roughly half the cells, the row-reversal visits every cell once. O(1) extra space — every swap happens directly on the input matrix.

🔑 The Key Insight

The brute force's rotation formula is correct, but computing it directly requires writing into cells that haven't been "vacated" yet — you'd overwrite data you still need unless you park the whole result somewhere else first. Transpose-then-reverse sidesteps this entirely: a transpose is a pure pairwise swap (matrix[i][j] only ever trades places with matrix[j][i], and nothing else touches either cell), so it's always safe to do directly on the original storage. Reversing each row afterward is likewise just a sequence of local, self-contained swaps. Two safe, in-place passes replace one pass that wasn't safe to do in place at all.

🔗 Related Chapters

  • Arrays and Strings — the 2-D array being mutated in place; the same nested-array indexing discipline as any grid problem.
  • Matrix Traversal — the layer-by-layer / diagonal-by-diagonal walk over a 2-D grid that this transpose-and-reverse decomposition builds on.

🧸 Memory Sentence

Rotate Image is flipping a photo across its diagonal, then mirroring each row — two cheap in-place moves that add up to a clean 90-degree turn, no second photo required.

✅ Check Your Understanding

  1. The transpose loop only swaps matrix[i][j] with matrix[j][i] for j > i. What would go wrong — or become redundant — if the inner loop instead ran over all of 0..<n, including j <= i?
  2. Trace the corner element matrix[0][0] = 1 through both steps (transpose, then reverse each row) and confirm it lands in the position a 90-degree clockwise rotation would put it.
  3. If you transposed the matrix and then reversed each column instead of each row, what rotation would you get instead of clockwise — and why does swapping which axis gets mirrored flip the rotation's direction?
  4. Why does the brute-force formula rotated[j][n - 1 - i] = matrix[i][j] need a completely separate matrix to write into, while the transpose-and-reverse approach never does?

⬅️ Previous: Minimum Interval to Include Each Query · Next: Spiral Matrix ➡️

Clone this wiki locally