What it is
Matrix questions in this bank are not graph-traversal problems (no flood fill, no shortest path) — they're about manipulating a fixed 2D grid in place: rotating it, zeroing rows and columns, walking it in a spiral, or exploiting sortedness across rows and columns to search faster than checking every cell. The core skill is coordinate bookkeeping: writing down exactly how (row, col) maps to a new position or a new value, and doing that transformation without an extra grid when the interviewer asks for in-place.
When it applies
- The grid's structure itself (fixed dimensions, row/column sortedness, geometric symmetry) is the thing being exploited, not connectivity between cells.
- You're asked to transform the grid in place — rotate, reflect, zero out — under an O(1) or no-extra-grid space constraint.
- Rows and/or columns are individually or jointly sorted, and you can use that order to search faster than a full scan, or to binary search over a virtual flattened view.
- If the question instead asks about regions, adjacency, or shortest paths between cells, that's the graph/grid-traversal pattern, not this one — the giveaway is whether "neighboring cells" matters at all to the answer.
Tells in the problem
- "Rotate 90 degrees... in place, without allocating another grid" — a hint that the transformation decomposes into two simpler in-place operations (e.g. transpose then reverse).
- "Set the entire row and column to zero" with an in-place, constant-extra-space requirement — a hint to store the marker inside the grid itself rather than in separate row/column sets.
- Both rows and columns are individually sorted, or the whole grid reads as one sorted sequence when flattened — a hint for binary search over a computed index rather than a linear scan.
- "Return elements in clockwise/counterclockwise order" with a shrinking boundary shape (spiral) — track four shrinking edges rather than trying to track direction changes ad hoc.
- Updating "simultaneously" from current state (every cell's next value depends on the current values of its neighbors) — a hint you need to distinguish old values from new ones without a second grid.
The classic mistake
Corrupting the very data you still need to read — overwriting a cell with a new value (a rotated position, a zero marker, a new generation's state) before every other cell that depends on the original value has been read — is the mistake that shows up most. This happens because in-place transformations look like simple loops, and it's easy to write the update before double-checking whether some other iteration of the same loop — or the next row's computation — still needs the original value. The fix is to identify, before writing any code, which values are read-after-write hazards, and either process in an order that avoids the conflict (corners inward, four cells at a time for rotation) or use an in-band marker (like negating a value, or using a placeholder distinct from the domain) to record "new" state without erasing the "old" state prematurely.
Questions to start with
- Spiral Matrix — pure coordinate bookkeeping: four shrinking boundaries, no in-place mutation hazard to worry about.
- Rotate Image — the canonical in-place transform, and the clearest case of "don't overwrite a cell before you've read it."
- Set Matrix Zeroes — forces you to record which rows/columns to clear without a separate structure, using the grid's own first row and column.
- Search a 2D Matrix — treats a fully sorted grid as one flattened array to binary search over.
- Game of Life — the hardest read-after-write hazard: every cell's next state depends on neighbors that are also being updated.