DSA Flood Fill

The problem

Flood fill recolours one connected region of a grid. A region is a set of cells that share one colour and reach each other through side neighbours. The fill starts at one given cell and paints every cell of its region with a new colour.

Cells of the same colour elsewhere do not change. Only the region that touches the start cell is painted. The code below prints two grids and states what one fill does to each.

first = [["a", "a", "b"], ["a", "b", "b"], ["c", "c", "b"]]
second = [["1", "1", "2"], ["1", "2", "2"], ["2", "2", "1"]]
for row in first:
    print("".join(row))
print("fill from (0, 0) with x: the three a cells become x")
print()
for row in second:
    print("".join(row))
print("fill from (2, 2) with 9: only the bottom-right 1 becomes 9")

The first region holds three a cells at the top left. The b and c cells keep their colours. In the second grid, the bottom-right 1 is cut off from the other 1 cells by 2 cells, so it forms a region of one.

Intuition

The first idea replaces a colour everywhere. Every cell that holds the start colour gets the new colour. That idea ignores connection, and connection is the whole problem.

The second grid exposes the flaw. Its bottom-right 1 shares a colour with three 1 cells at the top left and touches none of them. A global replace paints all four. A true fill paints only the one cell in the start region.

def show(grid):
    for row in grid:
        print("".join(row))

grid = [["1", "1", "2"], ["1", "2", "2"], ["2", "2", "1"]]
start = grid[2][2]
for r in range(len(grid)):
    for c in range(len(grid[0])):
        if grid[r][c] == start:
            grid[r][c] = "9"
show(grid)
print("cells painted: 4, correct count: 1")

Four cells changed and three of them are wrong. Reachability, not colour alone, defines the region. The fill must travel from neighbour to neighbour and stop wherever the colour changes.

Brute force

A careful route travels with a queue and an explicit visited set. Start with the start cell in the queue. Take a cell out, paint it, and queue its side neighbours that still hold the start colour and were never visited.

The route is correct. It is clumsy because the visited set duplicates information the grid itself could hold. A painted cell already differs from the start colour, so the set is a second record of the same fact.

from collections import deque

def brute_fill(grid, sr, sc, new_colour):
    start = grid[sr][sc]
    if start == new_colour:
        return grid, 0
    seen = set()
    queue = deque([(sr, sc)])
    seen.add((sr, sc))
    painted = 0
    while queue:
        r, c = queue.popleft()
        grid[r][c] = new_colour
        painted += 1
        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]):
                if grid[nr][nc] == start and (nr, nc) not in seen:
                    seen.add((nr, nc))
                    queue.append((nr, nc))
    return grid, painted

grid = [["a", "a", "b"], ["a", "b", "b"], ["c", "c", "b"]]
grid, painted = brute_fill(grid, 0, 0, "x")
for row in grid:
    print("".join(row))
print("cells painted:", painted)

The result matches the expected fill. The visited set ends holding every painted cell, a copy of what the repainted grid already shows. The optimal fill drops the set and lets the new colour itself mark a cell as done.

The optimal solution: recolour as the visited mark

The key idea is one sentence. Recolour each cell the moment the fill reaches it, so the new colour itself proves the cell is done and no visited set is needed.

One guard comes first. If the new colour equals the start colour, the fill returns at once. Without that guard, a recoloured cell would still match the start colour and the fill would revisit it forever.

def flood_fill(grid, sr, sc, new_colour):
    start = grid[sr][sc]
    if start == new_colour:
        return grid
    def fill(r, c):
        if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]):
            return
        if grid[r][c] != start:
            return
        grid[r][c] = new_colour
        fill(r + 1, c)
        fill(r - 1, c)
        fill(r, c + 1)
        fill(r, c - 1)
    fill(sr, sc)
    return grid

def show(grid):
    for row in grid:
        print("".join(row))

first = [["a", "a", "b"], ["a", "b", "b"], ["c", "c", "b"]]
show(flood_fill(first, 0, 0, "x"))
print()
second = [["1", "1", "2"], ["1", "2", "2"], ["2", "2", "1"]]
show(flood_fill(second, 2, 2, "9"))

Both cases from the first section match. The first fill paints the three a cells and nothing else. The second paints one cell, because its region holds one cell.

Walkthrough

Follow the fill on the first grid, starting at the top-left cell. The region is the three a cells. The trace prints the grid after each cell is painted, in the order the recursion reaches them.

grid = [["a", "a", "b"], ["a", "b", "b"], ["c", "c", "b"]]
start = grid[0][0]

def show():
    for row in grid:
        print("".join(row))
    print()

def fill(r, c):
    if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]):
        return
    if grid[r][c] != start:
        return
    grid[r][c] = "x"
    print("painted", (r, c))
    show()
    fill(r + 1, c)
    fill(r - 1, c)
    fill(r, c + 1)
    fill(r, c - 1)

print("start grid:")
show()
fill(0, 0)

The fill paints the start cell first, then moves down to the a below it, then right to the a beside the start. Each neighbour that holds b or c refuses and returns. After three paints no a in the region remains, and every further call stops at the colour test.

Complexity

Time is O(k) for a region of k cells. Each cell in the region is painted once, and each paint checks four neighbours, so the work grows with the region alone and not with the whole grid.

Space is O(k) in the worst case. The recursion stacks one call per cell along the current path, and a snaking region can stack every cell. The brute-force queue route pays the same order of space, split between its queue and its visited set.

def counted(grid, sr, sc, new_colour):
    start = grid[sr][sc]
    painted = 0
    if start == new_colour:
        return 0
    def fill(r, c):
        nonlocal painted
        if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]):
            return
        if grid[r][c] != start:
            return
        grid[r][c] = new_colour
        painted += 1
        fill(r + 1, c)
        fill(r - 1, c)
        fill(r, c + 1)
        fill(r, c - 1)
    fill(sr, sc)
    return painted

for size in [2, 3, 4]:
    grid = [["a"] * size for _ in range(size)]
    print("grid", size, "x", size, "cells painted:", counted(grid, 0, 0, "x"))

A pure single-colour grid is one region, so every cell paints. The painted count equals the cell count at each size. A region smaller than the grid costs less, which the single-cell fill in the second case already showed.

Edge cases and pitfalls

The equal-colour fill is the dangerous case. The new colour equals the start colour, so the guard returns the grid unchanged at once. Skipping the guard loops forever, because a painted cell still matches the start colour and gets visited again and again.

A single cell is a region of one. A whole grid of one colour is one region that covers everything. A start cell boxed in by other colours paints alone, with all four neighbour calls refusing.

def flood_fill(grid, sr, sc, new_colour):
    start = grid[sr][sc]
    if start == new_colour:
        return grid
    def fill(r, c):
        if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]):
            return
        if grid[r][c] != start:
            return
        grid[r][c] = new_colour
        fill(r + 1, c)
        fill(r - 1, c)
        fill(r, c + 1)
        fill(r, c - 1)
    fill(sr, sc)
    return grid

def show(grid):
    for row in grid:
        print("".join(row))

same = [["a", "a"], ["a", "a"]]
print("new colour equals start colour:")
show(flood_fill(same, 0, 0, "a"))
print("single cell:")
show(flood_fill([["a"]], 0, 0, "x"))
print("whole grid one region:")
show(flood_fill([["b", "b"], ["b", "b"]], 1, 1, "z"))
print("boxed-in start:")
show(flood_fill([["a", "b"], ["b", "b"]], 0, 0, "x"))

Each grid behaves as its region dictates. The equal-colour grid comes back untouched, which is the guard doing its one job. The boxed-in start changes one cell, because every neighbour holds a different colour.