leetExpert
Matrix · grid algorithms in production · overview

Anything laid out in rows and columns is a matrix. Your systems are full of them.

Eight lessons of grid algorithms, and eight systems that run them every second: the memory your screen is drawn from, the alert grouping that wakes you at 3 a.m., the router that lays out the wires on a chip.

systems 8scenes 8every frame run, not drawn

Where a cell lives: one line of arithmetic

A grid is drawn in rows and columns, but memory is one line. In a grid with C columns, cell (r, c) sits at r × C + c: skip r whole rows, then step c into the row. The first system reads memory in that order and the second runs the arithmetic backwards, from a flat position to a row and a column.

Neighbours: a list of offsets and one bounds check

Many grid questions are about a cell and the cells touching it. Writing the touching cells as a short list of offsets, with one bounds check, turns the corners and edges from special cases into cells that simply have fewer neighbours.

Working in place: the order of the writes

Some grids are too large to copy. Working in place means no write may destroy something a later step still has to read, so the order of the writes is the whole technique.

Walking a grid: a little state, kept exact

Some problems fix the order the cells are visited in: a spiral from the outside in, or a path that has to spell something. The state that tracks the walk is small, four bounds or one mark per cell on the path, and keeping it exact is what makes the walk correct.

Recognise the shape

Four questions point you at the right grid technique before any code is written.