Transforming a grid in place

Rotations and traversals, done with coordinate identities rather than by pushing indexes around until the tests pass.

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.

1grid = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]2 3transposed = [list(row) for row in zip(*grid)]4print("start:     ", grid)5print("transposed:", transposed)6print("rows then reversed:", [row[::-1] for row in transposed])

Two familiar operations compose into the rotation. Doing either in place is the part left to write.

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.

1top, bottom = 0, 0        # one row2left, right = 0, 2        # three columns3 4print(f"top pass covers columns {left} to {right}")5top += 16print(f"boundaries now: top={top}, bottom={bottom}, left={left}, right={right}")7print("right pass covers rows", list(range(top, bottom + 1)), "-> nothing")8right -= 19print("bottom pass guarded by top <= bottom:", top <= bottom)

Without that guard the single row would be walked forward and then backward, duplicating every value.

Find the bug· 5 min

Find the transpose bug

This is meant to reflect a square grid across its main diagonal, in place. It returns the grid completely unchanged. Click the line that is wrong.

Click the line you think is wrong

Problem· 22 min

Rotate Image

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

Problem· 25 min

Spiral Matrix

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

Problem· 28 min

Set Matrix Zeroes

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1grid = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]2 3transposed = [list(row) for row in zip(*grid)]4print("start: ", grid)5print("transposed:", transposed)6print("rows then reversed:", [row[::-1] for row in transposed])

1top, bottom = 0, 0 # one row2left, right = 0, 2 # three columns3 4print(f"top pass covers columns {left} to {right}")5top += 16print(f"boundaries now: top={top}, bottom={bottom}, left={left}, right={right}")7print("right pass covers rows", list(range(top, bottom + 1)), "-> nothing")8right -= 19print("bottom pass guarded by top <= bottom:", top <= bottom)