132. Flood Fill with BFS

Why this mechanism works

Changing the worklist changes exploration order, not component membership. FIFO expands cells in nondecreasing hop distance from the start, while LIFO follows a deeper frontier first. Marking at enqueue time remains essential in either traversal.

State and boundaries

queue contains discovered recolored cells awaiting expansion in discovery order. original is the target component color.

Protocol

1. Handle empty or unchanged-color input.
2. Recolor and enqueue the start.
3. Remove the oldest queued cell.
4. Discover original-color neighbors by recoloring before enqueue.
5. Continue until the queue empties.

Visualization

start -> distance 1 neighbors -> distance 2 neighbors
FIFO preserves this layer order
final recolored component matches DFS

Python implementation

from collections import deque

def flood_fill_bfs(image, sr, sc, color):
    if not image or not image[0]:
        return image
    original = image[sr][sc]
    if original == color:
        return image
    rows, cols = len(image), len(image[0])
    queue = deque([(sr, sc)])
    image[sr][sc] = color
    while queue:
        r, c = queue.popleft()
        for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and image[nr][nc] == original:
                image[nr][nc] = color
                queue.append((nr, nc))
    return image

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L4 flood_fill_bfs: if not image or not image[0]:
image=[[1, 1, 0], [1, 0, 1]]; sr=0; sc=0; color=2

L6 flood_fill_bfs: original = image[sr][sc]
image=[[1, 1, 0], [1, 0, 1]]; sr=0; sc=0; color=2; original=1

L9 flood_fill_bfs: rows, cols = len(image), len(image[0])
image=[[1, 1, 0], [1, 0, 1]]; sr=0; sc=0; color=2; original=1; rows=2; cols=3

L10 flood_fill_bfs: queue = deque([(sr, sc)])
image=[[1, 1, 0], [1, 0, 1]]; sr=0; sc=0; color=2; original=1; rows=2; cols=3; queue=deque([(0, 0)])

L11 flood_fill_bfs: image[sr][sc] = color
image=[[2, 1, 0], [1, 0, 1]]; sr=0; sc=0; color=2; original=1; rows=2; cols=3; queue=deque([(0, 0)])

L13 flood_fill_bfs: r, c = queue.popleft()
image=[[2, 1, 0], [1, 0, 1]]; sr=0; sc=0; color=2; original=1; rows=2; cols=3; queue=deque([]); r=0; c=0

L14 flood_fill_bfs: for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
image=[[2, 1, 0], [1, 0, 1]]; sr=0; sc=0; color=2; original=1; rows=2; cols=3; queue=deque([]); r=0; c=0; dr=1; dc=0

L15 flood_fill_bfs: nr, nc = r + dr, c + dc
image=[[2, 1, 0], [1, 0, 1]]; sr=0; sc=0; color=2; original=1; rows=2; cols=3; queue=deque([]); r=0; c=0; dr=1; dc=0; nr=1; nc=0

... 24 intermediate state changes omitted ...

L14 flood_fill_bfs: for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
image=[[2, 2, 0], [2, 0, 1]]; sr=0; sc=0; color=2; original=1; rows=2; cols=3; queue=deque([]); r=0; c=1; dr=0; dc=1; nr=-1; nc=1

L15 flood_fill_bfs: nr, nc = r + dr, c + dc
image=[[2, 2, 0], [2, 0, 1]]; sr=0; sc=0; color=2; original=1; rows=2; cols=3; queue=deque([]); r=0; c=1; dr=0; dc=1; nr=0; nc=2

L14 flood_fill_bfs: for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
image=[[2, 2, 0], [2, 0, 1]]; sr=0; sc=0; color=2; original=1; rows=2; cols=3; queue=deque([]); r=0; c=1; dr=0; dc=-1; nr=0; nc=2

L15 flood_fill_bfs: nr, nc = r + dr, c + dc
image=[[2, 2, 0], [2, 0, 1]]; sr=0; sc=0; color=2; original=1; rows=2; cols=3; queue=deque([]); r=0; c=1; dr=0; dc=-1; nr=0; nc=0

L4 flood_fill_bfs: if not image or not image[0]:
image=[[3]]; sr=0; sc=0; color=3

L6 flood_fill_bfs: original = image[sr][sc]
image=[[3]]; sr=0; sc=0; color=3; original=3

Why the solution is correct

The same component reachability argument as DFS proves that exactly the connected original-color region is recolored. FIFO order additionally ensures each discovery layer is expanded before the next layer, which will matter when distance becomes the output.

Time and space

O(R*C) worst-case time and O(R*C) queue space.

Common mistakes

Using list.pop(0) introduces shifting cost. Switching to a queue does not justify delaying the discovery mark until removal.

Reasoning card

Transfer exercise

Return the number of BFS layers needed to reach the farthest cell in the recolored component.