Flood Fill Algorithm: Working, Explanation, and Image Processing Applications

I’ve used the flood fill algorithm every time I’ve clicked the “paint bucket” tool in an image editor, even before I knew what it was called. It’s the technique behind filling in a connected region of a grid or image with a new color, and I find it a wonderful example of how a simple recursive or iterative idea, applied to a grid, produces a very visible and intuitive result. Beyond image editors, I’ve come to appreciate that flood fill is really just graph traversal (DFS or BFS) applied to pixels, and that framing is what makes it click for me conceptually.

History and Background

I trace flood fill back to early computer graphics work in the 1970s and 1980s, closely tied to the development of raster graphics and paint programs. It doesn’t have a single named inventor the way KMP or Kadane’s algorithm does — instead, it emerged naturally as programmers building the first bitmap paint tools (like early versions of MacPaint in 1984) needed an efficient way to fill enclosed regions with color. Over time, it became a standard topic in introductory computer science and graphics courses because it’s such a direct, hands-on application of graph traversal concepts like depth-first and breadth-first search.

Problem Statement

I’m given a 2D grid (commonly representing an image, where each cell is a pixel with a color value) along with a starting cell and a new color. I need to change the color of the starting cell and all cells connected to it that share the same original color, using either 4-directional or 8-directional connectivity, without touching cells of a different color. The problem is fundamentally about identifying and modifying a connected component in a grid, and it needs to be efficient enough to handle large images without excessive memory use or stack overflow.

Core Concepts

• Connectivity: defines which neighboring cells are considered “connected” — commonly 4-connectivity (up, down, left, right) or 8-connectivity (including diagonals).
• Target color: the original color of the starting cell, which determines which neighboring cells are eligible to be filled.
• Replacement color: the new color to apply to the connected region.
• Connected component: the maximal set of cells reachable from the start cell through same-colored, connected neighbors.
• Seed point: the starting cell from which the fill begins.

How It Works

I approach flood fill in one of two equivalent ways:

1. Recursive (DFS-based) flood fill: starting at the seed cell, I check if its color matches the target color; if so, I change it to the replacement color, then recursively call the same operation on all valid neighboring cells.
2. Iterative (BFS or stack-based) flood fill: I use an explicit queue or stack to hold cells to process, avoiding the call-stack overhead and depth limitations of recursion, which matters a great deal for large images.

In both approaches, I always check three conditions before processing a cell: it must be within grid bounds, it must currently have the target color, and it must not already have been changed to the replacement color (to avoid infinite loops, especially important if target and replacement colors are ever the same).

Working Principle

The underlying mechanism is a graph traversal where each pixel is a node, and edges connect pixels that are adjacent (by the chosen connectivity rule) and share the same original color. Flood fill essentially discovers the entire connected component containing the seed pixel and relabels every node in that component. This is exactly the same idea as finding connected components in graph theory, just specialized to the regular grid structure of an image, where adjacency is implicit from coordinates rather than an explicit edge list.

Mathematical Foundation

I can express the region to be filled formally as the connected component C containing the seed pixel p_0 in the grid graph G, where two pixels p_i and p_j are adjacent if and only if they are grid-neighbors (per the chosen connectivity) and share the same original color T:

$$ C = { p \in V : \exists \text{ a path } p_0 \to p \text{ in } G \text{ using only pixels of color } T } $$

The algorithm’s job is to set the color of every pixel in C to the replacement color R. Since a graph traversal like DFS or BFS visits every node in a connected component exactly once (when properly marking visited/filled nodes), the total work is proportional to the size of the component:

$$ T(|C|) = O(|C|) $$

which, in the worst case, is O(R x Col) for an R x Col grid, if the entire grid is one connected region of the target color.

Diagrams

flowchart TD
    A[Start at seed pixel] --> B{Pixel color == target color?}
    B -- No --> C[Do nothing, return]
    B -- Yes --> D[Set pixel color = replacement color]
    D --> E[For each valid neighbor: recursively call flood fill]
    E --> F[Return]

Pseudocode

function floodFill(grid, row, col, targetColor, replacementColor):
    if row < 0 or row >= numRows(grid) or col < 0 or col >= numCols(grid):
        return
    if grid[row][col] != targetColor:
        return
    if targetColor == replacementColor:
        return   // avoid infinite recursion when colors match

    grid[row][col] = replacementColor

    floodFill(grid, row - 1, col, targetColor, replacementColor)  // up
    floodFill(grid, row + 1, col, targetColor, replacementColor)  // down
    floodFill(grid, row, col - 1, targetColor, replacementColor)  // left
    floodFill(grid, row, col + 1, targetColor, replacementColor)  // right

Iterative version using a stack:

function floodFillIterative(grid, startRow, startCol, targetColor, replacementColor):
    if targetColor == replacementColor:
        return
    if grid[startRow][startCol] != targetColor:
        return

    stack = [(startRow, startCol)]
    while stack is not empty:
        (r, c) = stack.pop()
        if r, c out of bounds or grid[r][c] != targetColor:
            continue
        grid[r][c] = replacementColor
        stack.push((r-1, c))
        stack.push((r+1, c))
        stack.push((r, c-1))
        stack.push((r, c+1))

Step-by-Step Example

Consider this small grid, where I want to flood fill starting at (1,1), changing color 1 (T) to color 2:

Before:            After flood fill from (1,1), target=1, replacement=2:
1 1 0               2 2 0
1 1 0               2 2 0
0 0 0               0 0 0

Trace: I start at (1,1), which has color 1, matching the target. I change it to 2, then check its four neighbors: (0,1) has color 1, so I recurse there and change it to 2; (2,1) has color 0, so I skip it; (1,0) has color 1, recurse and change to 2; (1,2) has color 0, skip. Continuing this process from each newly filled cell, I eventually reach and fill (0,0) as well, since it connects through (0,1) and (1,0). The final result changes the entire top-left 2×2 block of 1s to 2s, while leaving all 0 cells untouched.

Time Complexity

• Best case: O(1) if the seed pixel doesn’t match the target color, or if the target and replacement colors are the same.
• Average case: O(k), where k is the number of pixels in the connected region being filled.
• Worst case: O(R x Col) for an R x Col grid, when the entire grid is one connected region of the target color — every cell is visited exactly once.

Space Complexity

For the recursive version, the space complexity is O(k) in the worst case due to the call stack depth, which can be as large as the number of pixels in the region — this can cause stack overflow on very large images. For the iterative version using an explicit stack or queue, the space complexity is also O(k), but it avoids the risk of exceeding the language’s call-stack limits, since the data structure lives on the heap rather than the call stack.

Correctness Analysis

I prove correctness by observing that the algorithm performs a standard graph traversal (DFS or BFS) over the grid graph restricted to same-colored pixels, and such traversals are well known to visit every node reachable from the start exactly once, provided visited nodes are properly marked (in this case, marking is implicit — once a pixel’s color is changed to the replacement color, it will no longer match the target color check, preventing revisits). By induction on the traversal order, every pixel in the connected component of the seed pixel is eventually visited and recolored, and no pixel outside that component is touched, since the boundary condition grid

Advantages

• Conceptually simple and maps directly to well-understood graph traversal techniques.
• Naturally supports both 4-connectivity and 8-connectivity by adjusting the neighbor-generation step.
• Easy to adapt for various applications beyond images, such as puzzle games (Minesweeper’s empty-cell reveal) or geographic region labeling.
• The iterative version scales well to large grids without recursion depth concerns.

Disadvantages

• The naive recursive version can cause stack overflow on large, densely connected regions.
• Basic flood fill can be slow on very large images compared to specialized “scanline fill” algorithms, which fill entire horizontal runs at once instead of pixel by pixel.
• Doesn’t handle anti-aliased or gradient-colored boundaries well, since it relies on exact color matching.
• Needs careful handling of the edge case where target and replacement colors are equal, or it will recurse infinitely (or, in the iterative version, loop indefinitely without the equality check).

Applications

• Paint bucket / fill tool in image editing software like Photoshop, GIMP, and MS Paint.
• Revealing connected empty regions in Minesweeper-style games.
• Region labeling and connected component analysis in computer vision and medical image segmentation.
• Geographic information systems (GIS), for filling or labeling contiguous map regions such as countries or lakes.
• Maze and puzzle generation/solving, to verify connectivity of open regions.

Implementation in C

#include <stdio.h>

#define ROWS 3
#define COLS 3

int grid[ROWS][COLS] = {
    {1, 1, 0},
    {1, 1, 0},
    {0, 0, 0}
};

void floodFill(int r, int c, int targetColor, int replacementColor) {
    /* Bounds check */
    if (r < 0 || r >= ROWS || c < 0 || c >= COLS) return;

    /* Only fill cells matching the target color */
    if (grid[r][c] != targetColor) return;

    /* Avoid pointless recursion if colors are identical */
    if (targetColor == replacementColor) return;

    grid[r][c] = replacementColor;

    floodFill(r - 1, c, targetColor, replacementColor); /* up */
    floodFill(r + 1, c, targetColor, replacementColor); /* down */
    floodFill(r, c - 1, targetColor, replacementColor); /* left */
    floodFill(r, c + 1, targetColor, replacementColor); /* right */
}

void printGrid() {
    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLS; j++) {
            printf("%d ", grid[i][j]);
        }
        printf("\n");
    }
}

int main() {
    printf("Before flood fill:\n");
    printGrid();

    int startRow = 1, startCol = 1;
    int targetColor = grid[startRow][startCol];
    int replacementColor = 2;

    floodFill(startRow, startCol, targetColor, replacementColor);

    printf("\nAfter flood fill:\n");
    printGrid();

    return 0;
}

#include <stdio.h>

#define ROWS 3
#define COLS 3

int grid[ROWS][COLS] = {
    {1, 1, 0},
    {1, 1, 0},
    {0, 0, 0}
};

void floodFill(int r, int c, int targetColor, int replacementColor) {
    /* Bounds check */
    if (r < 0 || r >= ROWS || c < 0 || c >= COLS) return;

    /* Only fill cells matching the target color */
    if (grid[r][c] != targetColor) return;

    /* Avoid pointless recursion if colors are identical */
    if (targetColor == replacementColor) return;

    grid[r][c] = replacementColor;

    floodFill(r - 1, c, targetColor, replacementColor); /* up */
    floodFill(r + 1, c, targetColor, replacementColor); /* down */
    floodFill(r, c - 1, targetColor, replacementColor); /* left */
    floodFill(r, c + 1, targetColor, replacementColor); /* right */
}

void printGrid() {
    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLS; j++) {
            printf("%d ", grid[i][j]);
        }
        printf("\n");
    }
}

int main() {
    printf("Before flood fill:\n");
    printGrid();

    int startRow = 1, startCol = 1;
    int targetColor = grid[startRow][startCol];
    int replacementColor = 2;

    floodFill(startRow, startCol, targetColor, replacementColor);

    printf("\nAfter flood fill:\n");
    printGrid();

    return 0;
}

Sample Input and Output

Input:

Grid:
1 1 0
1 1 0
0 0 0
Seed: (1,1), Replacement color: 2

Output:

Before flood fill:
1 1 0
1 1 0
0 0 0

After flood fill:
2 2 0
2 2 0
0 0 0

Optimization Techniques

• Scanline fill: instead of processing one pixel at a time, I can fill entire horizontal spans of matching pixels in one step, then only push the start of each new span found in adjacent rows onto the stack — this dramatically reduces the number of stack operations on large uniform regions.
• Iterative over recursive: for production code handling large images, I always prefer the stack/queue-based iterative version to eliminate call-stack overflow risk.
• Bitmask visited tracking: for very large grids, using a compact bitmask or boolean array to track visited cells (in cases where in-place color modification isn’t desirable) can save memory and improve cache performance.
• Parallel/tiled flood fill: for extremely large images, dividing the image into tiles and processing flood fill in parallel across tiles, then merging boundary results, can significantly speed up execution on multi-core systems.

Common Mistakes

• Forgetting the check for targetColor == replacementColor, which causes infinite recursion or infinite loops when the fill color matches the existing color.
• Using recursion on large grids without considering stack depth limits, leading to crashes on production-sized images.
• Not validating grid boundaries before accessing neighbor cells, resulting in out-of-bounds memory access.
• Mixing up 4-connectivity and 8-connectivity requirements, leading to incomplete or overly aggressive fills depending on the application’s needs.

Further Reading

• Foley, J. D., van Dam, A., Feiner, S. K., Hughes, J. F. “Computer Graphics: Principles and Practice,” Addison-Wesley: https://www.pearson.com/en-us/subject-catalog/p/computer-graphics-principles-and-practice/P200000003316
• GeeksforGeeks, “Flood fill Algorithm”: https://www.geeksforgeeks.org/dsa/flood-fill-algorithm/
• Wikipedia, “Flood fill”: https://en.wikipedia.org/wiki/Flood_fill
• LeetCode, “Flood Fill” problem (practical implementation practice): https://leetcode.com/problems/flood-fill/