Flood Fill Algorithm Explained: DFS, BFS and the Same-Colour Trap

Every image editor has a paint bucket: click a pixel and the whole patch of that colour changes at once. Behind it is flood fill, one of the first grid problems most people meet in an interview. The code is short, so the questions are about what goes wrong: a fill that never stops, a recursion that crashes on a large image, and a fill that leaks through diagonal gaps.

The problem it solves

You are given a grid of colours, a starting cell and a new colour. Repaint the starting cell and every cell connected to it, through up, down, left and right, that has the same original colour. Cells of that colour that cannot be reached without crossing a different colour stay as they are.

That last rule is the whole problem. "Repaint every A" is a loop over the grid. "Repaint every A you can walk to" is a graph search: each cell is a node, and each pair of neighbouring cells with the starting colour is an edge.

The intuition

Remember the starting colour, repaint the cell, then ask each of the four neighbours the same question: are you that colour too? Every neighbour that says yes repaints itself and passes the question on. The patch grows outwards until each branch stops at one of three things: the edge of the grid, a cell of another colour, or a cell already repainted.

The third stop is the clever part. Nobody keeps a visited set, because the new colour is the visited mark. A repainted cell no longer matches the starting colour, so the search cannot walk back into it.

Which is exactly why one check has to come first. If the new colour equals the starting colour, repainting changes nothing, every repainted cell still matches, and the search keeps walking the same cells forever. Compare the two colours before doing anything else, and return if they are the same.

The order in which cells are visited does not change the result. A stack gives depth-first search, which runs down one direction as far as it can before backing up. A queue gives breadth-first search, which grows the patch in rings around the click. Both paint exactly the same set of cells, because both visit everything reachable. Grid searches of this kind are listed in the patterns cheat sheet.

Watch it run

The animation starts with the paint bucket: click one cell, and the connected patch sharing its colour becomes the new one. It clicks a cell of colour A, and before painting anything it remembers the starting colour, because if that already equals the new one the recursion never ends. It repaints the cell, then visits its four neighbours; only the ones still holding A qualify. Each of those repaints itself and passes the question on, so the patch grows outwards one ring at a time. Rightwards it stops immediately, because that cell is B and not part of this patch. Down the left edge the same wall appears, B again, so that direction is finished too. One cell still leads somewhere: down the second column, into the corner below the wall. Its neighbours are both wall, so nothing new goes in, and seven cells are painted. The last frame points at the right-hand side: the same colour, still untouched, because a fill follows connections, not colour.

The code

The lesson's stack version, returning the number of painted cells, on the animation's canvas. Seven cells change and the A region right of the wall is left alone:

def flood(canvas, r, c, new):
    start = canvas[r][c]
    if start == new:                       # same colour: nothing would ever stop
        return 0
    painted, stack = 0, [(r, c)]
    while stack:
        y, x = stack.pop()
        if not (0 <= y < len(canvas) and 0 <= x < len(canvas[0])):
            continue                       # off the grid
        if canvas[y][x] != start:
            continue                       # a wall, or already repainted
        canvas[y][x] = new
        painted += 1
        stack += [(y - 1, x), (y + 1, x), (y, x - 1), (y, x + 1)]
    return painted

canvas = [list("AABAA"),
          list("AABAA"),
          list("AABAA"),
          list("BABAA")]
print(flood(canvas, 1, 0, "C"))            # 7
for row in canvas:
    print("".join(row))
# CCBAA
# CCBAA
# CCBAA
# BCBAA

The queue version paints a cell when it is added, not when it is taken out, so no cell is ever queued twice. The recursive version is the shortest to write and the first to break: a 200 by 200 region needs a call stack far deeper than Python's default limit of 1,000 frames, while both loops finish:

from collections import deque

def flood_bfs(canvas, r, c, new):
    start = canvas[r][c]
    if start == new:
        return 0
    rows, cols = len(canvas), len(canvas[0])
    canvas[r][c] = new                     # paint on the way IN, not on the way out
    queue, painted = deque([(r, c)]), 1
    while queue:
        y, x = queue.popleft()
        for ny, nx in ((y - 1, x), (y + 1, x), (y, x - 1), (y, x + 1)):
            if 0 <= ny < rows and 0 <= nx < cols and canvas[ny][nx] == start:
                canvas[ny][nx] = new       # painted now, so it is never queued twice
                queue.append((ny, nx))
                painted += 1
    return painted

def flood_recursive(canvas, y, x, start, new):
    if not (0 <= y < len(canvas) and 0 <= x < len(canvas[0])) or canvas[y][x] != start:
        return 0
    canvas[y][x] = new
    return 1 + sum(flood_recursive(canvas, ny, nx, start, new)
                   for ny, nx in ((y - 1, x), (y + 1, x), (y, x - 1), (y, x + 1)))

big = [["A"] * 200 for _ in range(200)]
print(flood_bfs([row[:] for row in big], 0, 0, "C"))     # 40000
print(flood([row[:] for row in big], 0, 0, "C"))         # 40000
try:
    flood_recursive([row[:] for row in big], 0, 0, "A", "C")
except RecursionError:
    print("RecursionError")                              # RecursionError

The same-colour trap, made visible. Without the guard, "repainting" A to A leaves every cell matching, so a 2 by 2 grid is still being searched after 100,000 pops, with a stack that keeps growing. And the connectivity rule matters: on a diagonal, a four-direction fill paints one cell where an eight-direction fill paints three:

def pushes_until(canvas, r, c, new, limit):
    """The lesson's loop WITHOUT the same-colour guard, stopped after `limit` pops."""
    start, stack, pops = canvas[r][c], [(r, c)], 0
    while stack and pops < limit:
        y, x = stack.pop()
        pops += 1
        if 0 <= y < len(canvas) and 0 <= x < len(canvas[0]) and canvas[y][x] == start:
            canvas[y][x] = new             # "repainted" to the same colour: still matches
            stack += [(y - 1, x), (y + 1, x), (y, x - 1), (y, x + 1)]
    return pops, len(stack)

print(pushes_until([list("AA"), list("AA")], 0, 0, "A", 100000))   # (100000, 166669)

def flood8(canvas, r, c, new):
    start = canvas[r][c]
    if start == new:
        return 0
    painted, stack = 0, [(r, c)]
    while stack:
        y, x = stack.pop()
        if 0 <= y < len(canvas) and 0 <= x < len(canvas[0]) and canvas[y][x] == start:
            canvas[y][x] = new
            painted += 1
            stack += [(y + dy, x + dx) for dy in (-1, 0, 1) for dx in (-1, 0, 1) if dy or dx]
    return painted

diagonal = ["ABB", "BAB", "BBA"]
print(flood([list(r) for r in diagonal], 0, 0, "C"),
      flood8([list(r) for r in diagonal], 0, 0, "C"))    # 1 3

Checked against a brute force with no stack, queue or recursion at all: it grows the painted set by sweeping the whole grid until a sweep adds nothing. All three fills must produce the same grid on 1,500 seeded random grids, including fills where the new colour equals the old:

import random

def brute(canvas, r, c, new):
    """Grow a painted set until nothing changes: no stack, no queue, no recursion."""
    start = canvas[r][c]
    if start == new:
        return [row[:] for row in canvas]
    rows, cols = len(canvas), len(canvas[0])
    region, changed = {(r, c)}, True
    while changed:
        changed = False
        for y in range(rows):
            for x in range(cols):
                if (y, x) not in region and canvas[y][x] == start and any(
                        (y + dy, x + dx) in region for dy, dx in ((1, 0), (-1, 0), (0, 1), (0, -1))):
                    region.add((y, x))
                    changed = True
    return [[new if (y, x) in region else canvas[y][x] for x in range(cols)] for y in range(rows)]

random.seed(24)
ok = True
for _ in range(1500):
    rows, cols = random.randint(1, 8), random.randint(1, 8)
    grid = [[random.choice("ABC") for _ in range(cols)] for _ in range(rows)]
    r, c, new = random.randrange(rows), random.randrange(cols), random.choice("ABC")
    want = brute(grid, r, c, new)
    for fill in (flood, flood_bfs):
        g = [row[:] for row in grid]
        fill(g, r, c, new)
        ok &= g == want
    g = [row[:] for row in grid]
    if grid[r][c] != new:
        flood_recursive(g, r, c, grid[r][c], new)
    ok &= g == want
print(ok)                                                # True

The complexity

• Time: O(R × C) in the worst case, when the region is the whole grid; in general, proportional to the region plus its border.
• Space: O(R × C) for the stack, queue or call stack in the worst case. Painting on entry keeps each cell in the queue at most once.
• No visited set: the repaint is the mark.

Where it goes wrong

• Skipping the same-colour check. The fill never terminates, or recurses until it crashes.
• Recursion on large regions. A region of tens of thousands of cells overflows the default call stack in Python and in many other languages. Use an explicit stack or queue.
• Checking bounds after reading the cell. Index first and a negative index silently wraps to the other side of a Python list.
• Mixing connectivity rules. Four directions and eight directions give different regions; say which one the problem wants.

When it shows up in interviews

The plain version is an easy question that rarely stays plain. The same search counts regions in number of islands, spreads from many starting points in rotting oranges, and starts from the border in "surrounded regions", where every region touching the edge survives. The choice between the two traversals is covered in DFS vs BFS.

How to say it in an interview

"I treat the grid as a graph where neighbouring cells of the starting colour are connected. I remember the starting colour and return immediately if it equals the new one, because otherwise repainted cells still match and the fill never stops. Then I use an explicit stack or queue: pop a cell, skip it if it is off the grid or not the starting colour, repaint it and push its four neighbours. The repaint doubles as the visited mark, so I need no extra set. It is O(R × C) time and space in the worst case, and I avoid recursion because a large region would overflow the call stack."