Matrix & Simulation

Intermediate · 18 min read · Problem-Solving Patterns, Design, Matrices & Advanced Topics

Spiral order, rotation, in-place markers and the Game of Life — index bookkeeping without bugs.

Matrix problems rarely need a clever algorithm. What makes them hard is bookkeeping: four boundaries, two indexes, and a dozen chances for an off-by-one. The fix is not to be more careful but to use a few fixed shapes that make the index arithmetic impossible to get wrong: shrinking boundaries, direction arrays,…

Tool 1: direction arrays

Never write four copies of "move up, down, left, right". Put the moves in an array and loop over it. Turning right is d = (d + 1) % 4:

Spiral order: shrinking boundaries

Keep the unvisited region as four boundaries. Walk one side, then move that boundary inward:

Rotate 90° in place: transpose, then reverse each row

Tracing where each cell goes during a four-way swap is error-prone. Two simple passes do the same job:

Set matrix zeroes: store markers inside the matrix

The obvious solution uses two boolean arrays to remember which rows and columns to clear. To get O(1) space, use row 0 and column 0 as those arrays. Then remember separately whether row 0 and column 0 themselves contained a zero:

Game of Life: encode two generations in one cell

Every cell updates from its eight neighbours at the same time. Updating in place naively means later cells see already-updated neighbours. The fix is to encode both "now" and "next" in the cell, using extra states:

Sorted rows and columns: the staircase search

Start at the top-right corner. If the current value is too big, everything below it in that column is bigger still, so drop the column. If it's too small, everything to its left in that row is smaller, so drop the row. Each step removes a whole row or column:

Practice ladder

Interview questions

  • How do you rotate an n × n matrix by 90 degrees clockwise in place?
  • In the staircase search, why start from the top-right corner?

Further reading

Key takeaways

  • Direction arrays replace four copies of movement code; turning is (d + 1) % 4.
  • Spiral: shrinking boundaries with two guard checks, or walk-and-turn when filling.
  • Rotate = transpose + reverse rows; set zeroes = markers in row 0 and column 0, applied last.
  • Simultaneous updates: encode the next state alongside the current one.
  • Sorted rows and columns: staircase search from the top-right corner, O(R + C).

Previous: Designing Data Structures · Next: Math for Interviews