Flood Fill — Solution

Problem

You have an image represented as a 2D grid of integers, where each integer is a pixel color. Given a starting pixel and a new color, repaint that pixel and every pixel reachable from it (moving up, down, left, or right) that shares the same original color.

• 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]]
• Explanation: All pixels with value 1 reachable from (1,1) via 4-directional moves are changed to 2; the isolated 1 at (2,2) is not reachable.

Intuition

From the starting pixel, the fill can spread only to neighbors that share the original color — any other color acts as a wall. This is simply a graph traversal where edges connect pixels of the same color. DFS (recursive or iterative) and BFS both work identically here; the recursive DFS maps most cleanly onto the problem's structure.

Solution — Recursive DFS

Capture the original color before modifying anything, then recursively paint every reachable same-colored pixel.

1. Record the starting pixel's original color; if it already equals the new color, return immediately to avoid infinite recursion.
2. Paint the current pixel with the new color (marking it as visited).
3. For each of the four neighbors (up, down, left, right): skip if out of bounds or not the original color.
4. Recurse into each valid neighbor.
5. Return the modified image after the initial call returns.

1from typing import List
2
3def floodFill(image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
4    original_color = image[sr][sc]
5    if original_color == color:  # already the target color — nothing to do
6        return image
7
8    rows, cols = len(image), len(image[0])
9
10    def dfs(row: int, col: int) -> None:
11        if row < 0 or row >= rows or col < 0 or col >= cols:
12            return
13        if image[row][col] != original_color:  # wall or already painted
14            return
15        image[row][col] = color  # paint before recursing to prevent revisiting
16        dfs(row + 1, col)
17        dfs(row - 1, col)
18        dfs(row, col + 1)
19        dfs(row, col - 1)
20
21    dfs(sr, sc)
22    return image

Time: O(m × n) — each pixel is visited and painted at most once.

Space: O(m × n) — the recursion stack can reach this depth when all pixels are the same color and form a single connected region.

Complexity Summary

Common Mistakes

• Not checking if the starting color already equals the new color. The recursive function would immediately repaint the pixel with the same color and then recurse into its neighbors — since the neighbor check sees the new color (which equals the original), nothing stops it. This causes infinite recursion and a stack overflow.
• Checking for the new color instead of the original color in the neighbor condition. Writing if image[row][col] == color: return would stop the DFS the moment it reaches a pixel it just painted, treating freshly filled pixels as walls and leaving the rest of the region untouched.
• Forgetting to capture original_color before the first paint. If you pass image[sr][sc] directly rather than storing it in a variable, and then paint that pixel on the first step, subsequent recursive calls see the new color at that position and may behave incorrectly.
• Using 8-directional neighbors instead of 4-directional. The problem specifies only up/down/left/right; including diagonals changes which pixels are considered connected and produces the wrong output.
• Checking bounds after indexing. Accessing image[row][col] before verifying that row and col are in range causes an index-out-of-bounds error. Always guard bounds first.

Related Problems

• number-of-islands — same DFS/BFS pattern to explore connected regions on a grid
• max-area-of-island — extends the region-counting idea to track the size of each connected component
• rotting-oranges — BFS spreading from multiple sources simultaneously, same grid connectivity model
• 01-matrix — multi-source BFS on a grid, finding shortest distance to nearest 0
• path-with-maximum-gold — DFS backtracking on a grid, exploring all reachable paths