Flood Fill: How the Paint Bucket Tool Actually Works

The core idea: a graph you never actually build

Flood fill answers one question: starting from a seed cell, which cells are reachable through same-colored neighbors? Recolor exactly that connected region and stop at the boundary. The elegant part is that you model the image as a graph without ever materializing one.

• Vertices = pixels (or grid cells, or Go board points).
• Edges = adjacency between two cells that share the target color — the color of the seed you clicked.
• The region = the connected component of the seed under that induced subgraph.

Because the graph is implicit, you generate neighbors on demand with arithmetic — (r±1, c) and (r, c±1) for 4-connectivity. The single load-bearing invariant is: every cell that has ever been pushed onto the frontier has already been recolored (marked). That mark IS the visited set. If you push before marking, a cell can enter the frontier twice, and in a cyclic grid graph that is not a mild slowdown — it is an infinite loop. Mark-on-enqueue, never mark-on-dequeue, is the difference between correct and hung.

Step by step, with pseudocode

The canonical iterative version uses an explicit stack (DFS) or queue (BFS). They differ only in which end you pull from; correctness is identical. Here is the DFS form:

floodFill(grid, sr, sc, newColor):
  target = grid[sr][sc]
  if target == newColor: return        # no-op guard, critical
  stack = [(sr, sc)]
  grid[sr][sc] = newColor               # mark seed on enqueue
  while stack not empty:
    (r, c) = stack.pop()
    for (nr, nc) in neighbors(r, c):    # 4- or 8-connected
      if inBounds(nr, nc) and grid[nr][nc] == target:
        grid[nr][nc] = newColor         # MARK before push
        stack.push((nr, nc))

The steps in words:

• Read the target color at the seed. Everything compares against this snapshot, not the live cell.
• Guard the no-op: if target == newColor, return immediately. Skip this and you loop forever — you overwrite a cell with the same color you are matching, so it stays “matchable” and gets re-pushed endlessly.
• Seed the frontier and mark the seed.
• Expand: pop a cell, and for each in-bounds neighbor still equal to target, recolor it and push it.
• Terminate when the frontier empties. Every reachable cell is now newColor.

Swap stack.pop() for queue.dequeue() and you have BFS, which fills outward in concentric rings (the wavefront) instead of plunging down one corridor.

Complexity: why it is exactly Θ(N)

Let N be the number of cells in the reachable region (not the whole image). Each cell is marked exactly once, so it is pushed once and popped once — the visited mark guarantees this. When a cell is processed, we inspect its constant number of neighbors: 4 or 8. So total work is Σ over N cells of O(1) neighbor checks = Θ(N) time.

• Time: Θ(N), and this is tight — you must touch every filled cell. In graph terms it is O(V + E), but on a grid E ≤ 4V (or 8V), so O(V + E) collapses to O(V) = Θ(N).
• Space: O(N) worst case for the frontier. A BFS on a solid rectangle holds a whole diagonal wavefront — up to O(√N·2) for a square but O(N) for a thin diagonal or comb shape. DFS on a spiral corridor can also stack O(N) frames.
• Best/worst split: if the seed color already equals the new color, the guard makes it O(1). Otherwise time is always Θ(N) — there is no “lucky” early exit for a fill.

The subtle cost is not asymptotic but peak memory. A 4096×4096 solid image is N ≈ 16.7 M cells. Recursive DFS wants ~16.7 M stack frames × ~64 bytes ≈ 1 GB of call stack — instant overflow. This is why production code is iterative or, better, span-based, which we cover next.

Scanline (span) filling: the version real paint tools ship

Naive flood fill pushes one cell per neighbor. That is a lot of stack churn. The scanline flood fill (popularized in Paul Heckbert's Graphics Gems, 1990, building on 1970s work) exploits image locality: instead of pushing individual pixels, it fills entire horizontal runs and pushes only spans to the stack.

• From a seed, scan left and right along the row, coloring the maximal contiguous run of target-colored pixels. This is a tight cache-friendly loop over contiguous memory.
• For the row above and the row below, walk the just-filled span and push a new seed only at the start of each new sub-span of target-colored pixels — not one per pixel.
• Repeat until the span stack empties.

The win is enormous in practice: the stack holds O(number of spans), which for typical images is orders of magnitude smaller than O(N). A solid rectangle degenerates to roughly two spans per row instead of N pushes. It is still Θ(N) time, but the constant factor and peak memory drop dramatically, and the inner run-fill is a sequential scan the CPU prefetcher loves — often 4–8× faster than per-pixel BFS. This is essentially what MS Paint and most 2D editors use.

Connectivity, tolerance, and the choices that change the answer

Flood fill has three policy knobs, and each silently changes the result:

• 4- vs 8-connectivity. 4-connected fills only orthogonal neighbors; 8-connected also crosses diagonals. This is not cosmetic — a checkerboard of two colors is a single 8-connected region but N separate 4-connected regions. In games like Go, capture uses 4-connectivity; diagonal “connection” is deliberately not a connection.
• The Jordan-curve trap. If you fill the region with 8-connectivity, its boundary must be treated with 4-connectivity, and vice versa, or a diagonal one-pixel gap will “leak” the fill through what looks like a closed outline. Paint tools that let color bleed through hairline cracks have this bug.
• Tolerance / fuzzy fill. Real paint buckets don't demand exact color equality — anti-aliased edges and JPEG noise mean pixels are near the target. The match test becomes ‖color(p) − target‖ ≤ tolerance under some metric (often per-channel or Euclidean in RGB/Lab). Photoshop's Magic Wand is flood fill with a tolerance threshold and an optional “contiguous” toggle that switches between region-connected fill and a global color-range select.

Two extra subtleties: compare against the original target color, never the live pixel (or the region eats itself), and if tolerance is used, be careful that A ≈ B and B ≈ C does not imply A ≈ C — tolerance chains can drift the fill far from the seed's color.

Where it runs at scale — and its cousins

Flood fill and its relatives are everywhere once you recognize the shape:

• Image editors: the paint bucket (exact fill) and Magic Wand (tolerance fill) in Photoshop, GIMP, Krita, MS Paint.
• Games: Minesweeper's cascade of empty cells on a click is a flood fill; Go/Reversi capture detection; connected-blob clearing in match-3 and Puyo; region reveal in map fog-of-war.
• Computer vision: cv2.floodFill in OpenCV for segmentation seeds and hole-filling; connected-component labeling is flood fill run once per unlabeled cell to tag every blob (used in OCR, particle counting, medical imaging).
• Maze/grid problems: “number of islands,” “surrounded regions,” and enclosed-area counting are all flood fill in an interview costume.

The intellectual neighbors are worth naming precisely. Flood fill is BFS/DFS restricted to a same-color component. Connected-component labeling = flood fill over all seeds. Multi-source BFS (fire spreading from many cells, or 01-BFS for weighted grids) generalizes the wavefront. And when the grid is static and you fill it many times, you can precompute components with Union-Find in near-linear O(N·α(N)) time, then answer “same region?” in effectively O(1) — the right tool when queries dominate fills.

Pitfalls, edge cases, and interview traps

The bugs cluster in a few predictable places:

• Missing the no-op guard. If newColor == target, an unguarded fill loops forever. This is the single most common LeetCode-style bug.
• Mark on dequeue, not enqueue. Marking when you pop lets a cell be pushed by multiple neighbors before it's processed — quadratic blowup or, with cycles, non-termination. Always mark the instant you push.
• Recursion depth. On large or thin regions, recursive DFS overflows the stack. Convert to an explicit stack, or use scanline. This is the #1 reason the “obvious” solution fails in production.
• Bounds and diagonal leaks. Off-by-one at image edges, and the 4-vs-8 boundary asymmetry from the Jordan-curve trap.
• Mutating the compare target. Comparing to the live pixel instead of the saved target color makes the fill unstable, especially with tolerance.
• In-place vs. copy. If callers need the original image, you must snapshot; the algorithm is destructive by design because the recolor IS the visited mark.

One classic optimization also deserves a caveat: reusing the output buffer as the visited set (recolor = mark) only works when the new color differs from the target — the very case the no-op guard protects. If they can be equal, you need a separate visited bitmap, which costs O(N) bits but restores correctness.

Flood fill strategies: same reachable set, very different constant factors and failure modes.

Strategy	Structure	Extra space	Failure mode
Recursive DFS	Call stack	O(N) frames	Stack overflow on large regions
Iterative DFS	Explicit stack (array)	O(N) cells	Peak memory = perimeter-ish
BFS	FIFO queue	O(N) cells	Wide frontier, high peak memory
Scanline (span) fill	Stack of spans	O(spans) ≪ O(N)	Tricky diagonal handling
Union-Find precompute	Disjoint set	O(N)	Overkill for one fill