Matrices

Careful boundary simulation, and encoding state in the grid itself.

Trigger in the prompt: 'Spiral', 'rotate', 'in place' on a two-dimensional grid.

mediumGame of Life

Apply one step of Conway's Game of Life to a grid, in place.

Trigger

'Simultaneous update', 'in place' — state encoding.

Approach
  1. Every cell must see the **old** state of its neighbours, so a naive in-place update is wrong.
  2. A copy is the easy answer — say it, then improve.
  3. Encode two states in one integer: use bit 0 for the current state and bit 1 for the next, then shift everything right in a second pass.
Target complexity

O(m · n) time, O(1) extra space.

Pitfall

Updating in place without encoding, so later cells read already-updated neighbours.

Say it out loud

“The update has to be simultaneous, so a naive in-place pass is wrong — later cells would read neighbours that already moved. A copy solves it in linear space; for constant space I encode both the old and the new state in the same integer using two bits, then shift in a second pass.”

Solve on LeetCode
mediumRotate Image

Rotate a square matrix 90 degrees clockwise, in place.

Trigger

'Rotate in place', 'no extra matrix'.

Approach
  1. Two steps: transpose, then reverse each row. State them before coding.
  2. Transpose only the upper triangle, or you undo your own work.
  3. The four-way cyclic-swap version is the alternative; the transpose-and-reflect version is far easier to get right under pressure.
Target complexity

O(n²) time, O(1) extra space.

Pitfall

Transposing the whole matrix instead of the upper triangle, which swaps everything back.

Say it out loud

“Transpose then reverse each row — two simple passes rather than one confusing four-way swap. The detail is only transposing above the diagonal; going over the whole matrix swaps each pair twice and leaves it unchanged.”

Solve on LeetCode
mediumSet Matrix Zeroes

Zero out the entire row and column of every zero in a matrix, in place.

Trigger

'In place' plus 'O(1) extra space' — the marker trick.

Approach
  1. The naive fix corrupts as it goes: zeroing immediately creates new zeros you then act on.
  2. Two marker arrays give O(m + n). The O(1) version uses the first row and column as those markers.
  3. Handle the first row and column separately with two boolean flags, since they are being used as storage.
Target complexity

O(m · n) time, O(1) extra space.

Pitfall

Zeroing during the scanning pass. Always mark first, then apply in a second pass.

Say it out loud

“The trap is zeroing as I scan, because the zeros I write look identical to the original ones. So: mark first, apply second. For constant space I use the first row and column as the marker storage, with two separate flags for those two lines since they can't mark themselves.”

Solve on LeetCode
mediumSpiral Matrix

Return the elements of a matrix in spiral order.

Trigger

'Spiral', 'clockwise traversal' — careful boundary simulation.

Approach
  1. Four boundaries: top, bottom, left, right. Walk one edge, then shrink that boundary.
  2. After each of the four passes, check whether the boundaries have crossed.
  3. The crossing check matters for non-square matrices — it is where this is failed.
Target complexity

O(m · n) time, O(1) extra space.

Pitfall

Omitting the boundary check between passes. A single-row or single-column remainder gets traversed twice.

Say it out loud

“Four boundaries that shrink as I complete each edge. The part I'll be careful with is checking for crossing between the passes — with a non-square matrix, a leftover single row would otherwise be walked twice.”

Solve on LeetCode