In-Place Transformations

Rearranging a grid without a second grid

Some grid problems don't traverse — they rewrite the grid into a transformed version of itself: transpose it, rotate it, flip it. The naive way is to allocate a fresh R × C grid, compute each output cell from the input, and return the new grid. That's correct and often fine. But a recurring constraint — stated outright in the next lesson's problem, Rotate Image — is do it in place, with O(1) extra space. This lesson builds the two in-place transforms you need (transpose and 90° rotation), proves why the rotation decomposes the way it does, and pins down exactly why "in place" is a meaningful demand here and not busywork.

We work with square grids (n × n) throughout, because in-place rotation requires it — a non-square rotation changes the shape, so its result can't overwrite the original's memory footprint. Transpose of a non-square grid is possible but produces a differently-shaped grid, so it too is an in-place operation only when square.

Transpose: reflect across the main diagonal

Picture a square patterned tile, held flat on a table, that you need to turn 90° clockwise without ever picking it all the way up — you can only slide small pieces of it around on the table's surface. One way to do it in two moves: first flip the tile over along its diagonal crease (top-left corner to bottom-right corner stays put, everything else swaps to its mirror position across that line), then flip each row of the now-diagonal-flipped pattern left-to-right. Do both, and the tile ends up rotated — without ever lifting it off the table into a second tile-sized space. That two-move trick is exactly what this lesson proves.

The transpose swaps rows with columns: cell (i, j) and cell (j, i) trade places. Equivalently, it reflects the grid across its main diagonal (the cells where i == j, which stay put). To do it in place, we swap each pair (i, j) ↔ (j, i) exactly once. The trap is swapping each pair twice — which returns the grid to its original state — so the inner loop must start at j = i + 1, touching only the cells strictly above the diagonal:

def transpose(matrix: list[list[int]]) -> None:
    n = len(matrix)
    for i in range(n):
        for j in range(i + 1, n):        # strictly upper triangle only
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

Why j = i + 1 and not j = 0? Each off-diagonal pair {(i, j), (j, i)} must be swapped once to exchange the two values. If the loop visited both (i, j) (with j > i) and later (j, i) (reached when the outer index is j and inner is i), it would swap the same pair a second time and undo the first swap. Starting the inner loop at i + 1 visits each unordered pair exactly once and leaves the diagonal (i == j) untouched, as it should be — diagonal cells are their own reflection.

The work is one swap per upper-triangle cell: there are n(n−1)/2 such cells, so transpose is O(n²) time (you must touch a constant fraction of all n² cells — unavoidable, since transposing genuinely relocates almost every value) and O(1) extra space (a single temporary per swap, which the tuple-swap hides).

90° rotation: transpose, then reverse each row

Rotating the grid 90° clockwise is the transform Rotate Image asks for. The elegant in-place method is a composition of two simpler in-place steps:

1. Transpose the grid (reflect across the main diagonal).
2. Reverse each row (reflect across the vertical center line).

We should not accept "transpose + reverse rows = rotate" on faith — the course's rule is that a composition like this gets proved, because the proof is exactly what tells you it's clockwise (and not counter-clockwise, which is a different pair of steps). Here is the index-level argument.

Take an n × n grid. Under a 90° clockwise rotation, the value at input position (r, c) must end up at output position (c, n−1−r) — the top row becomes the right column, which is what "clockwise" means at the level of coordinates. Now track a single value through the two steps and check it lands there:

Start: value V sits at (r, c).

Step 1 — transpose swaps (i, j) ↔ (j, i):
   V moves from (r, c)  →  (c, r).

Step 2 — reverse row c: column index x becomes (n − 1 − x),
   row index unchanged:
   V moves from (c, r)  →  (c, n − 1 − r).

Result: V is at (c, n − 1 − r)  ==  the clockwise-rotation target. ✓

Because this holds for an arbitrary (r, c), it holds for every value: the composition transpose-then-reverse-rows reproduces the clockwise rotation exactly. And the direction matters — swap the order or the reversal axis and you get a different rotation:

• Clockwise: transpose, then reverse each row.
• Counter-clockwise: transpose, then reverse each column (equivalently, reverse each row first, then transpose).

def rotate_clockwise(matrix: list[list[int]]) -> None:
    n = len(matrix)
    # Step 1: transpose in place.
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    # Step 2: reverse each row in place.
    for row in matrix:
        row.reverse()

Why in-place matters here specifically

"O(1) extra space" is not a generic virtue to chase everywhere — it's a demand that earns its weight in this setting for concrete reasons:

• The alternative allocates a whole second grid. Building the rotated result in a fresh array costs O(n²) auxiliary space — as much memory as the input itself. For a large image (grids here often are images), that can be the difference between fitting in memory and not. The in-place method needs only a scalar temporary per swap.
• It forces you to reason about aliasing. Doing it in place means every write lands in memory you're also reading from, so you must order the operations (transpose fully, then reverse) such that no step clobbers a value a later step still needs. The two-phase decomposition is what makes that safe — each phase is a set of independent swaps that don't interfere. This aliasing discipline is the transferable skill; the next lesson's Set Matrix Zeroes leans on the exact same "reuse the grid's own memory as scratch, carefully ordered" idea.

The trade is explicitness for memory. A from-scratch output grid is arguably easier to read (each output cell computed by one clear formula out[c][n-1-r] = in[r][c]), and if O(n²) extra space is acceptable, prefer it for clarity. In-place is the right call exactly when the space constraint is real — which, for grid-rewrite problems, it usually is stated to be.