BFS

Breadth-First Search on grids

repo ↗

BFS, but you can watch it spread

Three classic grid problems, each with a step-by-step animation: the queue, the expanding frontier, visited cells, and the matching code line. Press play, or step through with the arrow keys.

The one mental model behind all of these

BFS explores a grid in rings of equal distance from where it started. You keep a queue (first-in, first-out). You pop a cell, look at its neighbours, and push the ones you haven't seen yet. Because you always finish the closer cells before the farther ones, BFS naturally answers "shortest" and "how many layers" questions.

  1. Seed the queue with your start cell(s), and mark them seen.
  2. Pop the front. Process it.
  3. Push each valid, unseen neighbour; mark it seen when you push it (not when you pop it - that's the classic bug that revisits cells).
  4. Repeat until the queue is empty.
# the grid-BFS skeleton you reuse every time from collections import deque q = deque(starts) seen = set(starts) while q: r, c = q.popleft() for dr, dc in DIRS: # 4-dir or 8-dir nr, nc = r+dr, c+dc if in_bounds(nr,nc) and passable(nr,nc) and (nr,nc) not in seen: seen.add((nr,nc)) q.append((nr,nc))
200 · EASY-MED

Number of Islands

Count connected blobs of land. BFS flood-fills each island so it's counted once.

connectivity · flood fill
994 · MEDIUM

Rotting Oranges

Rot spreads each minute. Multi-source BFS: all sources start in the queue, layers = time.

multi-source · levels = time
1091 · MEDIUM

Shortest Path in Binary Matrix

Corner to corner in 8 directions. The first time BFS hits the goal is the shortest path.

shortest path · 8-dir

And memoization, one cell at a time

A different family: recursion that re-asks the same sub-problem over and over. The fix is to write each answer down once and reuse it. Watch the table fill, and watch the cache hits skip work.

The one mental model behind memoization

Memoization is just recursion + a notebook. Some problems have overlapping sub-problems: the plain recursion calls solve(state) for the same state an exponential number of times. So the first time you finish a state, you store the answer in a cache keyed by that state. Every later time it comes up, you read it back and skip the entire subtree underneath. Each state is computed exactly once.

  1. Key each sub-problem by its arguments (here: the pair of prefix lengths (i, j)).
  2. Check the cache first: if memo[key] exists, return it immediately.
  3. Recurse only on a miss, combining the smaller answers.
  4. Store the result under its key before returning, so the next caller gets a free lookup.
# the top-down DP skeleton you reuse every time memo = {} def solve(state): if is_base(state): # trivial answer, no recursion return base_value(state) if state in memo: # cache hit: skip the whole subtree return memo[state] memo[state] = combine(solve(s) for s in sub(state)) return memo[state]
72 · HARD

Edit Distance

Fewest inserts/deletes/replaces to match two words. A 2D memo table fills top-down; cache hits skip repeated work.

top-down DP · cache hits
Part of leetcode_droch. Tip: seed all sources first for multi-source BFS; mark seen on push, not on pop. For memoization: check the cache before recursing, and store before returning.