Flood Fill

Flood Fill is the algorithm behind the paint-bucket tool in every image editor. Click a pixel, and a whole connected blob of the same color flips to a new one. It is a clean, visual introduction to traversing a grid like a graph.

The slow way first

You might be tempted to scan the whole grid repeatedly, flipping any old cell next to an already-flipped one, looping until nothing changes. That works but wastes huge effort — it can re-scan the entire grid many times.

The better question: which cells actually belong to this region? They are exactly the cells you can reach from the seed by walking through same-color neighbors. That is a graph traversal — and we only need to visit each cell once.

The idea: treat the grid as a graph

Each cell is a node; its up/down/left/right neighbors are its edges. Run a depth-first search (DFS) from the seed. Pop a cell, repaint it, then push every in-bounds neighbor. Because a repainted cell no longer matches old, it gets skipped if it ever resurfaces — so the search naturally stops at walls and at cells already done.

The trick that keeps it correct: recoloring a cell to new is also how we mark it visited. A done cell no longer equals old, so the continue guard throws it away.

Walk through it

Step through the animation. We push the seed (0,0), then repeatedly pop, recolor, and push neighbors. Cells turn to the new color one by one as the stack drains. The two X cells are walls — they never match old, so the fill flows around them and stops cleanly when the stack is empty.

Pseudocode

old = color of the seed cell
if old == new: return grid          # nothing to do
push the seed onto a stack
while the stack is not empty:
    pop a cell (r, c)
    if grid[r][c] != old: skip it   # wall, or already recolored
    recolor grid[r][c] to new
    push all four in-bounds neighbors
return grid

The Python solution

def flood_fill(grid, sr, sc, new):
    old = grid[sr][sc]
    if old == new:
        return grid
    stack = [(sr, sc)]
    while stack:
        r, c = stack.pop()
        if grid[r][c] != old:
            continue
        grid[r][c] = new
        for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]):
                stack.append((nr, nc))
    return grid

• old is the seed color; everything we fill must match it.
• The if old == new guard avoids an infinite loop — without it, a recolored cell still equals old and gets pushed forever.
• stack holds the cells still to process; pop() makes this a depth-first search.
• The grid[r][c] != old check is the visited guard: walls and already-painted cells are skipped here.
• We push all in-bounds neighbors blindly; the guard at pop time filters out the bad ones, which keeps the code short.

Complexity

Each of the m·n cells is recolored once, and each is pushed a constant number of times (once per neighbor), so the work is linear in the grid size. The stack can hold up to O(m·n) cells in the worst case.

When this pattern shows up

Practice