Module A-9 — Grid Traversal Patterns: Flood Fill and Multi-Source BFS
What this module covers: Modules A-4 and A-5 already used a grid as an implicit graph informally, in passing. This module makes that framing explicit and puts it to work on two named patterns: flood fill (the algorithm behind an image editor's paint bucket tool) and multi-source BFS — starting a single breadth-first search from many points at once, which turns out to be meaningfully different from running several separate single-source searches.
A Grid Is a Graph With Implicit Edges
Every cell in a 2D grid is a node; its up/down/left/right neighbors (4-directional) — or additionally its four diagonal neighbors (8-directional) — are its edges. Nothing about DFS (Module A-4) or BFS (Module A-5) changes when applied to a grid; only how neighbors are generated changes, exactly as Module A-5's shortestPathInGrid already demonstrated.
typescript
Which set to use depends entirely on the problem's own rules — a rook moves 4-directionally, a king moves 8-directionally, and getting this wrong silently changes what counts as "connected."
Flood Fill: Paint Everything Connected
Flood fill starts at one cell and marks every cell reachable from it (through matching, connected cells) — precisely Module A-4's numIslands logic, generalized from "count islands" to "fill this specific region":
typescript
The if (originalColor === newColor) return grid guard is worth noticing specifically: without it, repainting a cell to the same color it already is would never trigger the grid[r][c] !== originalColor early return, since the color never actually changes — turning what should be a no-op into unbounded recursion. This is exactly the kind of edge case Module A-4's visited set handled explicitly for general graphs; here, the "already painted" check is the visited tracking, folded directly into the color comparison.
Multi-Source BFS: Seed the Queue With Every Source at Once
Rotting Oranges — a grid contains fresh oranges, rotten oranges, and empty cells; every minute, a rotten orange rots every fresh orange adjacent to it; find the minimum time for every fresh orange to rot (or determine it's impossible). The key move: seed the BFS queue with every initially-rotten orange simultaneously, not one at a time.
typescript
Compare this to running Module A-5's single-source BFS separately from each rotten orange: that would compute, for every fresh orange, its distance from one specific rotten orange — the wrong question, since an orange actually rots at the time the nearest rotten orange's spreading wave reaches it, not any single arbitrarily-chosen source. Seeding the queue with every source at minute 0 simultaneously means the BFS's normal layer-by-layer, enqueue-time-visited discipline (Module A-5) automatically resolves this correctly: whichever source's spreading wave reaches a given fresh orange first is, by definition of BFS's guarantee, the nearest one — every cell settles at its true minimum distance to the closest source, all computed in a single O(rows × cols) pass, rather than one BFS run per source.
Where This Shows Up in Your Stack
Image editors' paint bucket / magic wand tools are flood fill directly — clicking a pixel and having every connected, same-colored (or similarly-colored, with a tolerance threshold) region repaint or get selected together is exactly this module's floodFill function, operating on actual pixel data instead of a small integer grid.
Contagion and spread simulations (disease spread through a population grid, fire spreading through a forest map, a rumor propagating through a social network's adjacency structure) generalize Rotting Oranges' "everything currently affected spreads to its neighbors simultaneously, each step" pattern well beyond a literal grid of oranges.
"Distance to nearest facility" problems — nearest hospital, warehouse, or cell tower from every point on a map — are multi-source BFS directly: seed the queue with every facility location at distance 0, and the single BFS run computes every point's distance to its nearest facility in one pass, exactly the same efficiency gain Rotting Oranges demonstrates over running separate single-source searches.
Robot and game-AI pathfinding on grid maps frequently need "shortest distance to the nearest of several valid goal cells" (any exit, any collectible) — the same multi-source seeding trick, rather than computing distance to each goal separately and taking the minimum afterward.
Summary
A grid is a graph with implicit edges — neighbors generated by a 4- or 8-directional rule rather than read from an explicit adjacency list; DFS and BFS apply completely unchanged.
Flood fill is Module A-4's connected-region logic, with "already the target color" folded in as the visited check, and a same-color guard to prevent infinite recursion on a no-op fill.
Multi-source BFS seeds the queue with every starting point simultaneously, rather than running a separate BFS per source — this is what correctly computes each cell's distance to its nearest source in a single pass.
The efficiency gain is real and significant: one multi-source BFS run is O(rows × cols), versus O(k × rows × cols) for k separate single-source runs, one per source.
This pattern generalizes far beyond oranges: paint bucket tools, contagion/spread simulations, and nearest-facility distance maps are all the identical multi-source BFS shape.
The next module, Tries: Prefix Trees and Autocomplete, moves from grid- and general-graph traversal to a specialized tree built specifically for one job: fast prefix-based lookups on strings.
Knowledge Check
In floodFill, why does the function check if (originalColor === newColor) return grid; before starting the recursive fill, rather than relying solely on the grid[r][c] !== originalColor check inside fill?
Why does seeding the BFS queue with every rotten orange simultaneously (all at minute 0) produce the correct answer for "minimum time until every fresh orange rots," whereas running a separate single-source BFS from each rotten orange individually would not directly answer the same question?
According to the module, what is the efficiency comparison between one multi-source BFS run and running k separate single-source BFS searches (one per source) on a grid of size rows × cols?
Test your knowledge with more question sets
Sign in to access a wider variety of questions and get notified when new practice sets are added to this module.