Matrix traversal and rotation

33 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Read this 3 × 4 grid in a spiral, starting at the top-left and going clockwise:

With a finger you would trace the outer ring, 1 2 3 4 8 12 11 10 9 5, then the inner row, 6 7. Easy to do, surprisingly fiddly to program: the first attempt usually revisits a cell on the turn, or runs off the edge when the grid is a single row. The by-hand trick that does work is to think in rings: peel the outside ring, then the next ring, until nothing is left.

Build the structure, one piece at a time

The structure is four numbers that describe the ring still to be visited: top, bottom, left, right, the row and column indices of its edges. At the start they are 0, 2, 0, 3, the whole grid. Each ring is walked in four straight runs, and after each run the matching edge moves inwards by one:

1. Walk row top from left to right: 1 2 3 4. Then top becomes 1.
2. Walk column right from top to bottom: 8 12. Then right becomes 2.
3. If top ≤ bottom, walk row bottom from right to left: 11 10 9. Then bottom becomes 1.
4. If left ≤ right, walk column left from bottom to top: 5. Then left becomes 1.
5. Bounds are now top 1, bottom 1, left 1, right 2. Walk row 1 from 1 to 2: 6 7. Top becomes 2, which is past bottom, so stop.

The two "if" checks in steps 3 and 4 are what prevent a double visit when the remaining ring is a single row or a single column.

Rotating a square grid 90° clockwise is the cousin. Rather than moving each cell to a computed destination, do two simple passes: transpose (swap cell (i, j) with (j, i), which flips the grid over its main diagonal), then reverse every row. On a 2 × 2 grid [[1, 2], [3, 4]]: transpose gives [[1, 3], [2, 4]], reversing rows gives [[3, 1], [4, 2]], which is the grid turned clockwise.

Why it is correct

For the spiral, the invariant is that the four bounds enclose exactly the cells not yet visited, and every cell outside them has been output exactly once. Each run outputs the cells along one edge of that rectangle and then shrinks the matching bound, so the enclosed rectangle loses exactly the cells just output. The guards keep a degenerate rectangle (one row or one column left) from being walked twice in opposite directions. The loop ends when top passes bottom or left passes right, which means the rectangle is empty and every cell has been output.

For rotation, write a cell's position as (row, column). Transposing sends (i, j) to (j, i); reversing a row of length n then sends it to (j, n − 1 − i). A clockwise quarter turn of an n × n grid sends (i, j) to exactly (j, n − 1 − i), so the two passes together are the rotation.

Why it is fast

Each cell is output once in the spiral, so the time is the number of cells, O(m · n), with four integers of extra memory. The rotation does one swap per cell above the diagonal and one swap per pair in each row, about n² swaps in total, in place, with no second grid. The naive rotation that copies into a new grid also takes n² steps but needs n² extra memory, which is exactly the part interviewers ask you to avoid.

How to recognise it in an interview

Cues: "spiral order", "rotate the image in place", "diagonal order", "set the whole row and column to zero", "transpose". Say: "I will keep four shrinking bounds and walk one ring at a time", or "rotation is a transpose followed by reversing each row, done in place".

Spiral Matrix is the walk-through above; Spiral Matrix II fills the numbers 1 … n² into the same walk. Rotate Image is the transpose-then-reverse pair. Set Matrix Zeroes uses the first row and first column of the grid itself as the markers of which rows and columns must be cleared, so it needs no extra memory beyond two flags.

02The idea in one line

Rotate = transpose then reverse rows; spiral = four shrinking bounds.

Reach for it when: Rotate image, spiral matrix I/II, diagonal traverse, set matrix zeroes.

Cost: O(mn) time.

03The walk-through, step by step

The video works one example: Spiral Matrix on a 3×4 grid. These are its captions in order, so you can follow without the video or check a step you missed.

1. Keep four bounds; walk the outer ring, then shrink
2. Row 0 left→right, then top becomes 1
3. Column 3 top→bottom, then right becomes 2
4. Row 2 right→left, then bottom becomes 1
5. Column 0 bottom→top, then left becomes 1
6. Row 1 left→right, then top becomes 2
7. Bounds crossed: every cell visited exactly once
8. Rotation is the cousin: transpose, then reverse each row
9. O(m·n) time, output only

04Asked at Google

9 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Matrix: Staircase search in a sorted matrix.