Grids as graphs

Lesson · 11 min read · Graphs · Traversing a grid

A grid is a graph you never build: cells are nodes, neighbours come from coordinates. Depth-first fills a region; breadth-first measures distance.

A graph that is never written down

A large share of graph interview problems arrive as a grid: a map of land and water, a maze, a board, an image. Each cell is a node, and each cell's neighbours are the cells next to it. Nobody builds an adjacency list for this, because the neighbours of (r, c) can be computed from the coordinates whenever they are needed.

or→

Left: four neighbours, sharing a side. Right: eight, adding the diagonals. The problem statement says which.

The neighbours are listed with a pair of direction arrays, so one loop handles all of them:

DIRS = [(-1, 0), (0, 1), (1, 0), (0, -1)]          # up, right, down, left

def neighbours(r, c, rows, cols):
    for dr, dc in DIRS:
        nr, nc = r + dr, c + dc
        if 0 <= nr < rows and 0 <= nc < cols:      # in bounds
            yield nr, nc

constexpr int DIRS[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};   // up, right, down, left

std::vector<std::pair<int, int>> neighbours(int r, int c, int rows, int cols) {
    std::vector<std::pair<int, int>> out;
    for (auto [dr, dc] : DIRS) {
        int nr = r + dr, nc = c + dc;
        if (0 <= nr && nr < rows && 0 <= nc && nc < cols)      // in bounds
            out.push_back({nr, nc});
    }
    return out;
}

static final int[][] DIRS = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};   // up, right, down, left

static List<int[]> neighbours(int r, int c, int rows, int cols) {
    List<int[]> out = new ArrayList<>();
    for (int[] d : DIRS) {
        int nr = r + d[0], nc = c + d[1];
        if (0 <= nr && nr < rows && 0 <= nc && nc < cols)      // in bounds
            out.add(new int[] {nr, nc});
    }
    return out;
}

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

function* neighbours(r, c, rows, cols) {
    for (const [dr, dc] of DIRS) {
        const nr = r + dr, nc = c + dc;
        if (0 <= nr && nr < rows && 0 <= nc && nc < cols)      // in bounds
            yield [nr, nc];
    }
}

const DIRS: [(i32, i32); 4] = [(-1, 0), (0, 1), (1, 0), (0, -1)];   // up, right, down, left

fn neighbours(r: i32, c: i32, rows: i32, cols: i32) -> impl Iterator<Item = (i32, i32)> {
    DIRS.iter()
        .map(move |&(dr, dc)| (r + dr, c + dc))
        .filter(move |&(nr, nc)| 0 <= nr && nr < rows && 0 <= nc && nc < cols)   // in bounds
}

dirs :: [(Int, Int)]
dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]                    -- up, right, down, left

neighbours :: Int -> Int -> Int -> Int -> [(Int, Int)]
neighbours r c rows cols =
  [ (nr, nc) | (dr, dc) <- dirs, let nr = r + dr, let nc = c + dc
             , 0 <= nr, nr < rows, 0 <= nc, nc < cols ]       -- in bounds

With R rows and C columns there are n = R·C nodes and at most 4n edges, so every traversal below costs O(R·C).

Three checks before every step

Almost every bug in a grid traversal is one of three checks done late, done wrong, or forgotten. Before moving into a neighbour, confirm that it is:

inside the grid, checked first, before the cell is read;
passable: land rather than water, open rather than a wall, the right colour;
not yet visited.

Visited cells are tracked either in a separate boolean grid or by overwriting the cell in the input (turning land into water once it is counted). Overwriting saves memory and is common in interviews, but it destroys the input; ask before doing it, and do not do it when the caller needs the grid afterwards.

Depth-first search: filling a region

Depth-first search on a grid is the flood fill of a paint program: start in a cell and spread to every connected cell of the same kind. It answers "which cells belong to this region?", "how big is it?" and "does it touch the border?".

Depth-first flood fill

fill(r, c)

If (r, c) is outside the grid, not passable, or visited, return.
Mark (r, c) visited.
Call fill on the four neighbours: up, right, down, left.

Checking at the top of the call, rather than before each call, keeps the code short: every neighbour is passed in and the call itself rejects the bad ones. Below, the search fills the island that contains (0, 0). The numbers give the order in which cells are reached.

Flood fill from (0, 0); neighbours tried up, right, down, left.

Step 1 / 14

call stack (bottom → top)
(0,0)0
Start at (0,0): mark it visited.
Step 2 / 14

call stack (bottom → top)
(0,0)0(0,1)1
Move right to (0,1): it is in bounds, land and unvisited. Mark it (number 2).
Step 3 / 14

call stack (bottom → top)
(0,0)0(0,1)1(1,1)2
Move down to (1,1): it is in bounds, land and unvisited. Mark it (number 3).
Step 4 / 14

call stack (bottom → top)
(0,0)0(0,1)1(1,1)2(1,2)3
Move right to (1,2): it is in bounds, land and unvisited. Mark it (number 4).
Step 5 / 14

call stack (bottom → top)
(0,0)0(0,1)1(1,1)2(1,2)3(2,2)4
Move down to (2,2): it is in bounds, land and unvisited. Mark it (number 5).
Step 6 / 14

call stack (bottom → top)
(0,0)0(0,1)1(1,1)2(1,2)3(2,2)4(2,3)5
Move right to (2,3): it is in bounds, land and unvisited. Mark it (number 6).
Step 7 / 14

call stack (bottom → top)
(0,0)0(0,1)1(1,1)2(1,2)3(2,2)4(2,3)5(3,3)6
Move down to (3,3): it is in bounds, land and unvisited. Mark it (number 7).
Step 8 / 14

call stack (bottom → top)
(0,0)0(0,1)1(1,1)2(1,2)3(2,2)4(2,3)5
All four neighbours of (3,3) are water, outside the grid or visited: it is finished; back to (2,3).
Step 9 / 14

call stack (bottom → top)
(0,0)0(0,1)1(1,1)2(1,2)3(2,2)4
All four neighbours of (2,3) are water, outside the grid or visited: it is finished; back to (2,2).
Step 10 / 14

call stack (bottom → top)
(0,0)0(0,1)1(1,1)2(1,2)3
All four neighbours of (2,2) are water, outside the grid or visited: it is finished; back to (1,2).
Step 11 / 14

call stack (bottom → top)
(0,0)0(0,1)1(1,1)2
All four neighbours of (1,2) are water, outside the grid or visited: it is finished; back to (1,1).
Step 12 / 14

call stack (bottom → top)
(0,0)0(0,1)1
All four neighbours of (1,1) are water, outside the grid or visited: it is finished; back to (0,1).
Step 13 / 14

call stack (bottom → top)
(0,0)0
All four neighbours of (0,1) are water, outside the grid or visited: it is finished; back to (0,0).
Step 14 / 14

call stack (bottom → top)
empty0
All four neighbours of (0,0) are water, outside the grid or visited: it is finished. The region has 7 cells; the numbers give the order they were reached.

current cellon the call stackfinished

The cell (3, 1) is land but is never reached: it touches the island only diagonally, and these moves do not include diagonals. Counting islands is this fill run from every unvisited land cell; the pattern module on connected components does exactly that.

Breadth-first search: measuring distance

Run breadth-first search from a cell and each ring of the search is one move further away, so the search labels every reachable cell with its shortest distance. This is the method for "fewest moves through a maze", "minutes until every orange rots" and "distance to the nearest exit".

Breadth-first search from (0, 0) through open cells; # is a wall. Each cell shows its distance.

Step 1 / 9

queue: ring 0
(0,0)0
Start at (0,0) with distance 0.
Step 2 / 9

queue: ring 1
(0,1)0(1,0)1
Ring 1: 2 new cells, each one move from a cell of ring 0 and never seen before. Their distance is 1.
Step 3 / 9

queue: ring 2
(0,2)0(2,0)1
Ring 2: 2 new cells, each one move from a cell of ring 1 and never seen before. Their distance is 2.
Step 4 / 9

queue: ring 3
(1,2)0(3,0)1
Ring 3: 2 new cells, each one move from a cell of ring 2 and never seen before. Their distance is 3.
Step 5 / 9

queue: ring 4
(1,3)0(2,2)1(3,1)2
Ring 4: 3 new cells, each one move from a cell of ring 3 and never seen before. Their distance is 4.
Step 6 / 9

queue: ring 5
(1,4)0(3,2)1
Ring 5: 2 new cells, each one move from a cell of ring 4 and never seen before. Their distance is 5.
Step 7 / 9

queue: ring 6
(0,4)0(2,4)1
Ring 6: 2 new cells, each one move from a cell of ring 5 and never seen before. Their distance is 6.
Step 8 / 9

queue: ring 7
(3,4)0
Ring 7: 1 new cell, each one move from a cell of ring 6 and never seen before. Their distance is 7.
Step 9 / 9

queue: ring 7
empty0
No cell can be added: every open cell reachable from (0,0) carries its distance. Cells left blank cannot be reached.

the ring just addedreached earlier

Several starting cells at once (every rotten orange, every exit) need no new algorithm: put them all in the queue at distance 0 before the loop starts. That is multi-source breadth-first search.

Implementation and cost

The flood fill problem at the end of this module is the depth-first fill in its plainest form. Its solution in all six languages:

def flood_fill(image, sr, sc, color):
    old = image[sr][sc]
    if old == color:
        return image                    # nothing to do, and filling would never stop
    rows, cols = len(image), len(image[0])

    def fill(r, c):
        if r < 0 or c < 0 or r >= rows or c >= cols or image[r][c] != old:
            return                      # outside, another colour, or already repainted
        image[r][c] = color
        fill(r - 1, c)
        fill(r, c + 1)
        fill(r + 1, c)
        fill(r, c - 1)

    fill(sr, sc)
    return image

#include <functional>
#include <vector>

std::vector<std::vector<int>> solve(std::vector<std::vector<int>> image, int sr, int sc, int color) {
    const int old = image[sr][sc];
    if (old == color) return image;     // nothing to do, and filling would never stop
    const int rows = image.size(), cols = image[0].size();
    std::function<void(int, int)> fill = [&](int r, int c) {
        if (r < 0 || c < 0 || r >= rows || c >= cols || image[r][c] != old) return;
        image[r][c] = color;
        fill(r - 1, c); fill(r, c + 1); fill(r + 1, c); fill(r, c - 1);
    };
    fill(sr, sc);
    return image;
}

class Solution {
    private int[][] image;
    private int old, color;

    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        this.image = image;
        this.old = image[sr][sc];
        this.color = color;
        if (old != color) fill(sr, sc);     // equal colours: nothing to do
        return image;
    }

    private void fill(int r, int c) {
        if (r < 0 || c < 0 || r >= image.length || c >= image[0].length || image[r][c] != old) return;
        image[r][c] = color;
        fill(r - 1, c); fill(r, c + 1); fill(r + 1, c); fill(r, c - 1);
    }
}

function floodFill(image, sr, sc, color) {
  const old = image[sr][sc];
  if (old === color) return image;      // nothing to do, and filling would never stop
  const rows = image.length, cols = image[0].length;
  const fill = (r, c) => {
    if (r < 0 || c < 0 || r >= rows || c >= cols || image[r][c] !== old) return;
    image[r][c] = color;
    fill(r - 1, c); fill(r, c + 1); fill(r + 1, c); fill(r, c - 1);
  };
  fill(sr, sc);
  return image;
}

fn solve<const N: usize>(image: &[[i64; N]], sr: i64, sc: i64, color: i64) -> Vec<Vec<i64>> {
    let mut img: Vec<Vec<i64>> = image.iter().map(|row| row.to_vec()).collect();
    let old = img[sr as usize][sc as usize];
    if old == color {
        return img;                     // nothing to do, and filling would never stop
    }
    fn fill(img: &mut Vec<Vec<i64>>, r: i64, c: i64, old: i64, color: i64) {
        if r < 0 || c < 0 || r as usize >= img.len() || c as usize >= img[0].len() {
            return;
        }
        if img[r as usize][c as usize] != old {
            return;
        }
        img[r as usize][c as usize] = color;
        fill(img, r - 1, c, old, color);
        fill(img, r, c + 1, old, color);
        fill(img, r + 1, c, old, color);
        fill(img, r, c - 1, old, color);
    }
    fill(&mut img, sr, sc, old, color);
    img
}

import qualified Data.Map.Strict as M

solve :: [[Int]] -> Int -> Int -> Int -> [[Int]]
solve image sr sc color
  | old == color = image                 -- nothing to do
  | otherwise = [[M.findWithDefault 0 (r, c) final | c <- [0 .. cols - 1]] | r <- [0 .. rows - 1]]
  where
    rows = length image
    cols = length (head image)
    grid = M.fromList [((r, c), x) | (r, row) <- zip [0 ..] image, (c, x) <- zip [0 ..] row]
    old = grid M.! (sr, sc)
    final = fill grid (sr, sc)
    -- the map is the image; a repainted cell no longer matches old, so it is never revisited
    fill g (r, c) = case M.lookup (r, c) g of
      Just x | x == old -> foldl fill (M.insert (r, c) color g) [(r - 1, c), (r, c + 1), (r + 1, c), (r, c - 1)]
      _ -> g

The same code is the reference solution to Repaint a region of an image, where it is compiled and run against the tests in all six languages.

TimeO(R · C)

SpaceO(R · C)

Every cell is visited at most once and examines four neighbours. The recursive fill can go R·C calls deep, a snake-shaped region filling the grid; on a 1,000 × 1,000 grid that is a million frames, so use an explicit stack or breadth-first search when the grid is large.