Rotate Image — The Mural Turn

Boss 1: The Mural Turn

Seventeen dungeons down. One gate left.

Every dungeon so far handed you a data structure or an algorithm family and said "master this". The final dungeon is different. Math and Geometry bosses don't hide behind clever structures. They hide behind a fact: a symmetry, a pattern, an invariant sitting in plain sight. Once you see the math, the code collapses into bookkeeping. Miss it, and no amount of clever coding saves you.

Boss 1 is the purest example in the catalog. The entire fight is one geometric identity.

The story

The city museum has a prized mosaic mural: a perfect square of tiles, n rows by n columns. The new director walks in, tilts her head, and says the composition would look better rotated a quarter turn clockwise.

One problem. The tiles are mortared into a frame bolted to the wall. The frame cannot be turned, tilted, or taken down. And the workshop that made it is long gone, so there is no second frame to rebuild the mural onto.

What the restorers can do is pry individual tiles out and swap their positions within the frame. That's the whole toolkit: rearrange tiles inside the square they already occupy, until the mural reads as if the entire thing had been turned 90 degrees.

Same tiles. Same frame. New orientation.

The problem, dressed up properly

You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees clockwise. You must rotate the image in place, without allocating another 2D matrix.

LeetCode 48, "Rotate Image". A medium that shows up constantly in interviews, because it separates people who memorized an answer from people who can derive one.

The naive attempt

Forget the frame constraint for a second. Where does a tile actually go under a clockwise quarter turn?

Watch one tile. The top row of the old mural becomes the right column of the new one. Row i becomes column n-1-i, and a tile's column j becomes its new row. So the tile at row i, column j lands at row j, column n-1-i. With a second frame, that's the whole job:

def rotate_with_copy(matrix):
    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]
    return rotated

Correct, clean, O(n²) time... and it builds a second n-by-n frame. The story forbids exactly this, and so does the problem statement. O(n²) extra space is the thing we're here to kill.

But that mapping, (i, j) goes to (j, n-1-i), is the key to everything. Stare at it.

The weapon: transpose, then flip

Split the destination into two halves and the trick falls out:

• Going from (i, j) to (j, i) is a transpose: mirror the mural across its main diagonal (top-left to bottom-right).
• Going from (j, i) to (j, n-1-i) keeps the row and flips the column: that's reversing each row, a mirror across the vertical center line.

Chain them: transpose sends the tile to (j, i), then reversing row j carries it from column i to column n-1-i. Final position (j, n-1-i). Exactly the rotation. A quarter turn is two mirrors in a trench coat, and both mirrors are just swaps, which is all the frame allows.

Both mirrors are in-place swaps, so the code is short:

def rotate(matrix: list[list[int]]) -> None:
    n = len(matrix)
    # Mirror 1: transpose (swap across the diagonal)
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    # Mirror 2: reverse each row
    for row in matrix:
        row.reverse()

Note the inner loop starts at i + 1. The transpose only touches tiles above the diagonal and swaps each with its partner below. That's the mirror.

The second weapon: the four-way ring swap

Some interviewers follow up with "now do it in a single pass, moving each tile exactly once". That's the ring swap: peel the mural into square rings, and within each ring rotate tiles in cycles of four. Top goes to right, right to bottom, bottom to left, left to top, using one temporary tile-sized gap:

def rotate_rings(matrix: list[list[int]]) -> None:
    n = len(matrix)
    for layer in range(n // 2):
        first, last = layer, n - 1 - layer
        for i in range(first, last):
            offset = i - first
            top = matrix[first][i]                          # save top
            matrix[first][i] = matrix[last - offset][first]  # left -> top
            matrix[last - offset][first] = matrix[last][last - offset]  # bottom -> left
            matrix[last][last - offset] = matrix[i][last]    # right -> bottom
            matrix[i][last] = top                            # top -> right
    # same O(n^2) time, but each tile is written exactly once

Same complexity, more index arithmetic, more ways to bleed. Lead with transpose-and-reverse. Mention the ring swap exists, and pull it out only when asked. Knowing when each weapon is expected is part of the fight.

Watching it work

A 3-by-3 mural, tiles numbered so we can track them:

start          transpose      reverse rows
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

Check it against the mural on the wall. The old top row 1 2 3 now runs down the right edge, top to bottom. The old left column 1 4 7 became the new top row, reversed into 7 4 1. Tile 5 never moved, the center of a square doesn't under rotation. Tile 1 went from top-left to top-right, exactly where a clockwise turn sends it.

Two dumb mirrors. One perfect rotation.

Gotchas

1. Transposing with a full double loop. Run j from 0 instead of i + 1 and every pair gets swapped twice, landing right back where it started. Your "transpose" is the identity, your rotation is just row-reversal, and the output is a mirror image, not a turn. The diagonal split isn't an optimization, it's correctness.

2. Reversing the wrong axis. Transpose then reverse each column is a counterclockwise turn. So is reversing rows before transposing. The mirrors don't commute, and each pairing gives a different rotation. If your output looks rotated the wrong way, you almost certainly did one of these. Verify direction with a 2-by-2 like [[1,2],[3,4]] before trusting anything.

3. Ring-swap off-by-ones. The inner loop must stop before last, or the corner rotates twice. And the left-column read uses last - offset, not first + offset, because the left edge feeds the top in reverse order. This is why the ring swap eats candidates alive at the whiteboard: four coupled indices, one wrong and the mural scrambles silently.

4. Assuming it works on rectangles. A quarter turn of an m-by-n matrix produces an n-by-m matrix. Different shape, different frame, so "in place" is meaningless for rectangles. Every in-place trick here leans on the matrix being square. If an interviewer slides a rectangular grid at you, the answer is the naive copy, stated with confidence.

Complexity

Every tile gets touched a constant number of times: once in the transpose (as one half of a swap), once in the row reversal. The ring swap writes each tile exactly once.

Time: O(n²). Space: O(1).

You can't beat the time, n² tiles must move. And the story's whole point was beating the space.

Boss down

The director steps back, squints, and nods. The mural turned a quarter circle without ever leaving its frame, and the restorers never touched a second one. The trick was never about tiles. It was about seeing that one rotation is two mirrors, and mirrors are cheap.

That's the shape of this whole dungeon: find the math fact, and the code writes itself.

Next up, Boss 2: Spiral Matrix — The Spiral Plow. A field must be plowed in a spiral from the outside in, one continuous furrow, and the plow can never cross its own tracks. Walking a grid in a shrinking spiral sounds trivial until your boundaries start eating each other. See you inside the ring.