Transforming a grid in place

Key idea

A rotation is two easy operations

Rotating a square grid a quarter turn clockwise, in place, looks like it needs four-way element cycling with careful bounds. There is a much easier route: transpose the grid, then reverse each row.

Transposing swaps every cell with its mirror across the main diagonal, which is one nested loop with the inner starting at the outer index so each pair is swapped once. Reversing each row is one call per row.

Neither step needs any thought about bounds, and their composition is the rotation. Deriving a hard transformation as a composition of easy ones is the technique here.

Key idea

Traversals with shrinking boundaries

Walking a grid in a spiral is best written with four boundaries that close in, rather than with direction vectors and turn detection. Walk the top row, then the right column, then the bottom row, then the left column, shrinking a boundary after each.

The subtlety is that after shrinking, a later pass in the same lap may have nothing left to do, so the bottom and left passes need a guard checking that the boundaries have not crossed.

Watch the four boundaries on a single row, which is the input those guards exist for.

Why it works

Why only two of the four passes need a guard

The loop condition is checked before the top and right passes, so those are known to be valid. The top and right boundaries move during the lap, which is what can invalidate the bottom and left passes.

A single row and a single column are exactly the cases those guards exist for, which is why the trace above uses one. Without them, a single row is traversed forward and then backward, producing every value twice.

Key idea

Using the grid itself as storage

Some problems ask for a transformation using no extra space proportional to the grid. The move is to use part of the grid, usually the first row and column, as the marker storage.

It needs care: those cells serve two purposes at once, so whether the first row itself was affected has to be recorded separately before the markers are written, and the marked rows and columns must be applied before the first row and column themselves.

That ordering is the entire problem. Write the phases down in order before coding: record the edge cases, mark, apply to the interior, then apply to the edges.