131. Flood Fill with DFS

Why this mechanism works

Color equality defines which edges may be traversed. Mark a cell by recoloring it when discovered, before pushing it, so several neighbors cannot schedule it repeatedly. If the replacement equals the original color, this marking method cannot distinguish visited cells; return immediately because the desired output already exists.

State and boundaries

stack holds discovered recolored cells awaiting neighbor exploration. original is fixed from the starting cell.

Protocol

1. Handle empty input or unchanged color.
2. Recolor and push the start.
3. Pop one cell.
4. Recolor and push each in-bounds original-color neighbor.
5. Return the image after the stack empties.

Visualization

same-color component: explore through up/down/left/right
LIFO: newest discovered cell is expanded next
recolor before push = discovery mark

Python implementation

def flood_fill_dfs(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])
    stack = [(sr, sc)]
    image[sr][sc] = color
    while stack:
        r, c = stack.pop()
        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
                stack.append((nr, nc))
    return image

Worked execution

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

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

L4 flood_fill_dfs: original = image[sr][sc]
image=[[1, 1, 0], [1, 0, 1]]; sr=0; sc=0; color=2; original=1

L7 flood_fill_dfs: 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

L8 flood_fill_dfs: stack = [(sr, sc)]
image=[[1, 1, 0], [1, 0, 1]]; sr=0; sc=0; color=2; original=1; rows=2; cols=3; stack=[(0, 0)]

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

L11 flood_fill_dfs: r, c = stack.pop()
image=[[2, 1, 0], [1, 0, 1]]; sr=0; sc=0; color=2; original=1; rows=2; cols=3; stack=[]; r=0; c=0

L12 flood_fill_dfs: 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; stack=[]; r=0; c=0; dr=1; dc=0

L13 flood_fill_dfs: 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; stack=[]; r=0; c=0; dr=1; dc=0; nr=1; nc=0

... 24 intermediate state changes omitted ...

L12 flood_fill_dfs: 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; stack=[]; r=1; c=0; dr=0; dc=1; nr=0; nc=0

L13 flood_fill_dfs: 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; stack=[]; r=1; c=0; dr=0; dc=1; nr=1; nc=1

L12 flood_fill_dfs: 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; stack=[]; r=1; c=0; dr=0; dc=-1; nr=1; nc=1

L13 flood_fill_dfs: 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; stack=[]; r=1; c=0; dr=0; dc=-1; nr=1; nc=-1

L2 flood_fill_dfs: if not image or not image[0]:
image=[[1, 1]]; sr=0; sc=0; color=1

L4 flood_fill_dfs: original = image[sr][sc]
image=[[1, 1]]; sr=0; sc=0; color=1; original=1

Why the solution is correct

Every discovered neighbor is connected to the start through original-color cells, so no outside cell is recolored. Conversely, every cell in the component is eventually reached along such a path. Recoloring at discovery schedules each cell only once.

Time and space

O(R*C) worst-case time and O(R*C) worklist space; only the reached component is explored after initialization.

Common mistakes

Marking only when popping permits duplicate pending cells. Omitting the unchanged-color guard can create repeated scheduling indefinitely.

Reasoning card

Transfer exercise

Use a separate visited set instead of recoloring as the discovery mark, and compare state and mutation costs.