Matrix Traversal

A grid of cells: an image, a game board, a maze, a spreadsheet. Almost every question about one is a question about a graph you never had to build.

The trick that makes grid problems easy

A cell at (r, c) has neighbours at (r±1, c) and (r, c±1). Those are the edges. You never store them — you compute them:

const DIRECTIONS = [[-1, 0], [1, 0], [0, -1], [0, 1]] as const;   // up, down, left, right

for (const [dr, dc] of DIRECTIONS) {
  const [nr, nc] = [r + dr, c + dc];
  if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;     // off the edge
  // …visit (nr, nc)…
}

Write it this way every time. The alternative — four copy-pasted blocks for up, down, left and right — is where bounds-check bugs live, because you fix three of them and miss the fourth.

Diagonals? Add four entries. Nothing else changes.

const EIGHT = [[-1,-1], [-1,0], [-1,1], [0,-1], [0,1], [1,-1], [1,0], [1,1]] as const;

Once it is a graph, the usual tools apply

Flood fill / counting islands — depth-first or breadth-first search from every unvisited land cell:

function countIslands(grid: number[][]): number {
  const seen = grid.map((row) => row.map(() => false));
  let islands = 0;

  for (let r = 0; r < grid.length; r += 1) {
    for (let c = 0; c < grid[0]!.length; c += 1) {
      if (grid[r]![c] !== 1 || seen[r]![c]) continue;
      islands += 1;
      flood(grid, seen, r, c);      // marks this whole island as seen
    }
  }
  return islands;
}

Every cell is visited once across the entire run, so this is $O(rows \times cols)$ despite the nested loop containing a search.

Shortest path through a maze — breadth-first search, never depth-first. BFS reaches each cell in the fewest steps because it expands ring by ring; DFS finds a path, usually a ridiculous one.

Multi-source spread — rotting fruit, fire, water levels. Push every source into the queue before starting, and BFS naturally expands all of them in lockstep. This is a one-line change that people re-derive as something complicated.

When the order itself is the problem

Some grid questions are not searches. The answer is a specific traversal order, and the whole difficulty is bookkeeping.

Spiral order is the standard one. The clean way to think about it is four boundaries closing in:

function spiral(grid: number[][]): number[] {
  const out: number[] = [];
  let [top, bottom, left, right] = [0, grid.length - 1, 0, grid[0]!.length - 1];

  while (top <= bottom && left <= right) {
    for (let c = left; c <= right; c += 1) out.push(grid[top]![c]!);
    top += 1;
    for (let r = top; r <= bottom; r += 1) out.push(grid[r]![right]!);
    right -= 1;

    // These two need re-checking: the rows/columns above may have just met.
    if (top <= bottom) { for (let c = right; c >= left; c -= 1) out.push(grid[bottom]![c]!); bottom -= 1; }
    if (left <= right) { for (let r = bottom; r >= top; r -= 1) out.push(grid[r]![left]!); left += 1; }
  }
  return out;
}

Two index tricks worth knowing

Rotate 90° clockwise: transpose, then reverse each row.

for (let r = 0; r < n; r += 1)
  for (let c = r + 1; c < n; c += 1)          // c starts at r+1, or you swap back
    [grid[r]![c], grid[c]![r]] = [grid[c]![r]!, grid[r]![c]!];

for (const row of grid) row.reverse();

Transposing flips across the main diagonal; reversing flips left-to-right; the two together are a rotation. Doing it directly with a four-way cycle of indices is possible and nobody gets it right first time.

Flatten to one dimension. index = r * cols + c, and back out with r = Math.floor(index / cols), c = index % cols. This is what lets you use a union-find structure — which only knows about integers — on a grid.