Why does transposing a square grid then reversing each row rotate it a quarter turn clockwise?
answer
- A transpose is a mirror, not a turn
- Count how many mirrors a turn costs
- Which diagonal stays fixed under a transpose?
- After the mirror, one axis runs backwards
- Two reflections at 45 degrees make 90
basics
~20 sTransposing mirrors the grid across its main diagonal, which puts every element in its correct destination row but with the columns running backwards. Reversing each row fixes that order. Two mirrors at 45 degrees to each other compose into one quarter turn.
solid answer
~40 sTranspose sends the cell at `(r, c)` to `(c, r)` — a reflection across the main diagonal. Reversing each row of the result sends `(c, r)` to `(c, n-1-r)`. Compose them and the element at `(r, c)` lands at `(c, n-1-r)`, which is exactly the clockwise quarter turn: the first column read bottom-to-top becomes the first row. Geometrically, two reflections whose axes meet at 45 degrees compose to a rotation of 90 degrees, and because reflections do not commute the order picks the direction — reversing each row *first* and then transposing gives the counterclockwise turn instead. The recipe is popular because both steps stay inside the original square grid, so the rotation needs no second grid, and each step is separately easy to test.
go deeper
Memorise the direction check, not the recipe: the first column read bottom-to-top becomes the first row after a clockwise turn. Be ready to run a two-by-two example out loud to prove which way your steps turn the board.
Explain each step as a map on indices — transpose sends (r,c) to (c,r), row reversal sends (r,c) to (r,n-1-c) — and compose them to derive the destination rather than recalling it. Say why both steps stay in place.
Expect to be pushed onto shapes: odd side lengths, rectangular grids, and whether the caller still needs the original. Show that a shape change forces a copy and that you would write the destination index directly at that point.
Own the choice between this two-pass recipe and a single-pass ring cycle: the asymptotic cost is identical, so the decision is about which one your team can review and test correctly. Argue for the version whose halves are independently verifiable.
## The two steps, stated precisely For an `n x n` grid, write `(r, c)` for the cell in row `r`, column `c`, with indices from `0` to `n-1`. **Transpose** moves the value at `(r, c)` to `(c, r)`. That is a reflection across the main diagonal — the line from the top-left corner to the bottom-right corner. The diagonal cells `(k, k)` are fixed points: they do not move. **Reverse each row** moves the value at `(r, c)` to `(r, n-1-c)`. That is a reflection across the vertical centre line of the grid. ## Composing them Track one element. It starts at `(r, c)`. After the transpose it sits at `(c, r)`. Now reverse the row it is in: a cell at row `c`, column `r` moves to row `c`, column `n-1-r`. So the net map is ``` (r, c) -> (c, n-1-r) ``` That is the definition of a clockwise quarter turn. Sanity-check it on a two-by-two board holding `1 2 / 3 4`. Transpose gives `1 3 / 2 4`; reversing each row gives `3 1 / 4 2`. Turning the original a quarter turn clockwise, the left column read **bottom to top** (`3, 1`) becomes the top row — matching. That bottom-to-top reading is the fastest whiteboard check there is: after any claimed clockwise rotation, the first column of the input, read upwards, must equal the first row of the output. ## Why 45 degrees matters There is a clean geometric reason the recipe is exactly a quarter turn and not some other angle. Composing two reflections whose axes meet at an angle theta produces a rotation of `2 * theta`. The main diagonal and the vertical centre line meet at 45 degrees, so the composition is a 90-degree rotation. This also predicts the other transformations you might be asked for: | Goal | Recipe | Net map | |---|---|---| | Quarter turn clockwise | transpose, then reverse each row | `(r,c) -> (c, n-1-r)` | | Quarter turn counterclockwise | transpose, then reverse the *order of the rows* | `(r,c) -> (n-1-c, r)` | | Half turn | reverse the order of the rows, then reverse each row | `(r,c) -> (n-1-r, n-1-c)` | Reflections do not commute, and that is not a footnote — it is the whole reason direction is easy to get wrong. Reversing each row **first** and transposing **second** gives `(r, c) -> (r, n-1-c) -> (n-1-c, r)`, the counterclockwise turn. Same two operations, opposite result. ## Cost, and why this recipe is the default Each step is a linear pass over the grid: the transpose touches the roughly `n(n-1)/2` off-diagonal pairs once, and the row reversal swaps about `n/2` elements in each of `n` rows. Total work is `Theta(n^2)` with `O(1)` extra space. No rotation can beat `Omega(n^2)`, because every element outside the fixed centre must move. The recipe wins on correctness, not on speed: both halves stay inside the original square grid, so the whole rotation is in-place without a second grid, and each half is an operation you can test on its own. Its main rival — walking each concentric ring and cycling four cells at a time — makes the same asymptotic cost in a single pass but replaces two obvious loops with layer-and-offset index arithmetic that is a well-known bug factory. ## The two boundary cases interviewers probe **Odd side length.** When `n` is odd the centre cell `(n/2, n/2)` lies on both mirror lines, so it is a fixed point of the whole rotation and never moves. Nothing special is needed for it here; it matters mostly when someone writes the ring-cycling version and has to decide whether the innermost single-cell ring is included. **Non-square grids.** A grid with `m` rows and `n` columns transposes into one with `n` rows and `m` columns. The *shape* changes, so there is no in-place version at all — the result simply does not fit in the original footprint. You allocate a fresh `n x m` grid and write each element straight to its rotated destination in one pass; the two-step recipe buys nothing once a copy is unavoidable. ## The misconception to kill A transpose is a **mirror**, not a turn. Applying it alone leaves the grid reflected: reading the result feels rotated because the rows and columns have exchanged roles, but the mirror image of a board is not a rotated board. The row reversal is what converts one reflection into half of a rotation.
- What changes if the interviewer asks for the counterclockwise turn instead?Keep the transpose and reverse the *order of the rows* rather than the contents of each row — that sends `(r, c)` to `(n-1-c, r)`. Equivalently, reverse each row first and then transpose. Because reflections do not commute, simply swapping the order of the two original steps also flips the direction, which is the single most common slip at the whiteboard.
- Does this recipe still work on a grid with more rows than columns?Not in place. Transposing an `m x n` grid yields an `n x m` grid, so the result no longer fits the original footprint. You allocate a destination of the transposed shape and write each element directly to `(c, m-1-r)` in a single pass; the two-step decomposition buys nothing once you are copying anyway.
- What happens to the centre cell when the side length is odd?It stays exactly where it is. The centre lies on the main diagonal and on the vertical centre line, so both mirrors fix it, and therefore the rotation does too. It matters only when you write the ring-cycling variant and must decide whether the innermost one-cell ring is iterated — rotating it is a harmless no-op, but the loop bound is where people go off by one.
Hold a photo up to two mirrors angled 45 degrees apart: each mirror alone flips the picture, but bouncing through both comes back as a quarter turn.
saying these in an interview costs you the question
- Says a transpose by itself rotates the grid
- Reverses the order of the rows when asked for clockwise
- Claims the order of the two steps does not matter
- Thinks the recipe rotates a rectangular grid in place
- Cannot name which line the transpose mirrors across