Flood Fill

Flood Fill is an algorithm that determines and modifies a connected region of cells in a grid. Starting from a seed point, it expands outward to all reachable cells that share the same original value, replacing them with a new value. It is the algorithm behind the "paint bucket" tool found in virtually every image editing application, from Microsoft Paint to Adobe Photoshop. The algorithm has its conceptual origins in early computer graphics research of the 1970s, when raster displays became common and efficient region-filling techniques were needed. The earliest published descriptions appear in work by Smith (1979) on tint fill algorithms for computer graphics, and the basic technique has remained fundamentally unchanged for decades due to its simplicity and effectiveness.

How It Works

1. Start: Begin at the seed cell (the pixel or grid cell the user clicks on). Record its original value, which defines the region to be filled. If the seed cell already has the new fill value, stop immediately to avoid infinite processing.
2. Fill: Change the seed cell's value to the new fill value. This simultaneously marks it as visited and applies the desired change.
3. Expand: Check all 4-connected neighbors (up, down, left, right) of the current cell. For each neighbor that still has the original value and lies within the grid boundaries, add it to the processing stack (or queue).
4. Process: Pop the next cell from the stack, change its value to the new fill value, and check its neighbors. Each cell is processed exactly once because its value changes upon filling, ensuring it will not match the original value if encountered again.
5. Boundary: The fill naturally stops at region boundaries. A boundary is any cell that either has a different value from the original, lies outside the grid, or has already been filled. When the stack is empty, all reachable cells of the original value have been filled.

4-Connected vs. 8-Connected

A key design choice in flood fill is the neighborhood definition. 4-connected flood fill considers only the four cardinal neighbors (up, down, left, right), meaning the fill cannot cross diagonal gaps. 8-connected flood fill includes the four diagonal neighbors as well, allowing the fill to spread through diagonal connections. The choice matters significantly in practice. In image editors, 4-connected fill produces tighter boundaries that respect thin diagonal lines, while 8-connected fill can "leak" through single-pixel diagonal boundaries. Most paint bucket implementations use 4-connected fill by default, sometimes offering 8-connected as an option. The decision mirrors a fundamental concept in digital topology: under 4-connectivity, a diagonal line of pixels forms a connected barrier, but under 8-connectivity, the fill can pass through the gaps between diagonal pixels.

Implementation Variants

There are three common implementations of flood fill. Recursive DFS is the simplest to code, just a function that fills the current cell and recursively calls itself on valid neighbors. However, recursion depth can equal the number of filled cells, causing stack overflow on large regions (a 1000x1000 image could require a million stack frames). Iterative stack-based DFS replaces the call stack with an explicit stack data structure, avoiding stack overflow while maintaining the same depth-first exploration pattern. BFS with a queue explores the region in expanding wavefronts from the seed point, which can produce smoother visual animations. A fourth, more advanced variant is the scanline algorithm, which fills horizontal runs of pixels at a time and only pushes seed points for adjacent rows, reducing the number of stack operations and improving cache performance. Scanline flood fill is the preferred implementation in production image editors.

Complexity

Where N x M is the grid size. Every cell is visited at most once during the fill process. The space complexity arises from the stack or queue, which in the worst case (an entirely uniform grid) may hold O(N x M) entries. The scanline variant reduces practical space usage significantly but retains the same worst-case bounds.

When to Use

Flood Fill is used in image processing for the paint bucket tool, magic wand selection, and matte compositing. In game development, it powers territory detection in strategy games, procedural terrain generation, and solving puzzles like Minesweeper (revealing empty regions). It serves as a building block for connected component labeling in computer vision, where distinct objects in an image are identified and tagged. The algorithm also appears in maze-solving (filling dead ends), circuit board analysis (identifying copper regions), and geographic information systems (delineating drainage basins or flood zones). Any problem that requires identifying or modifying all cells reachable from a starting point through same-valued connections is a flood fill problem.