733 - Flood Fill

Difficulty: Easy | Pattern: DFS / BFS on Grid | Company tags: Facebook, Amazon, Google

Problem Statement

An image is represented by an m x n integer grid image where image[sr][sc] represents the pixel value of the image.

You are given three integers sr, sc, and color. Perform a flood fill starting from image[sr][sc]:

1. Change image[sr][sc] to color
2. Change any adjacent pixel (4-directional) of the same original color
3. Repeat for all such pixels

Return the modified image.

Example:

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]

Approach: DFS — O(m×n)

Key insight: Record the original color before changing anything. DFS from the start pixel, changing all connected pixels with the original color to the new color. Guard against the edge case where original_color == color (infinite loop).

def floodFill(image: list[list[int]], sr: int, sc: int, color: int) -> list[list[int]]:
    original = image[sr][sc]
    if original == color:
        return image  # already the target color; nothing to do
    
    rows, cols = len(image), len(image[0])
    
    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if image[r][c] != original:
            return
        image[r][c] = color
        dfs(r+1, c)
        dfs(r-1, c)
        dfs(r, c+1)
        dfs(r, c-1)
    
    dfs(sr, sc)
    return image

Dry Run

image = [[1,1,1],[1,1,0],[1,0,1]], sr=1, sc=1, color=2, original=1

Step	Call	Change
1	dfs(1,1)	image[1][1]=2
2	dfs(2,1)	image[2][1]=0 ≠ 1, return
3	dfs(0,1)	image[0][1]=2
4	dfs(1,2)	image[1][2]=0 ≠ 1, return
5	dfs(1,0)	image[1][0]=2
6	from (0,1): dfs(0,0), dfs(0,2)	image[0][0]=2, image[0][2]=2
7	from (1,0): dfs(0,0) already 2, dfs(2,0)	image[2][0]=1 → 2

Result: [[2,2,2],[2,2,0],[2,0,1]] ✓

Alternative: BFS

from collections import deque

def floodFill(image, sr, sc, color):
    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

Edge Cases

• original == color → return immediately (no change needed, avoids infinite recursion)
• Single-pixel image → change it and return
• Start pixel surrounded by different colors → only change that one pixel
• Entire grid same color → change everything

Complexity

• Time: O(m × n) — each pixel visited at most once
• Space: O(m × n) — recursive call stack or BFS queue in worst case

Related: LeetCode 200 (Number of Islands) uses the same DFS/BFS grid traversal pattern but counts components instead of recoloring.