Flood Fill DSA Solution

Learning Outcome

After this lesson, you should be able to capture the original color and DFS only through matching neighboring pixels.

Problem Statement

Given an image, a start row, a start column, and a new color, recolor the connected region that has the same original color.

Input	Output	Why
`image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2`	`[[2,2,2],[2,2,0],[2,0,1]]`	Only pixels connected to the start cell with the original color are recolored.

Brute Force Approach

Repeatedly scan the whole image after recoloring each pixel. This adds unnecessary passes and still needs boundary logic.

Optimized Approach

Store the original color. If it already equals the new color, return. Otherwise DFS through matching four-direction neighbors.

Exact Pseudocode

oldColor = image[start]
if oldColor equals newColor:
  return image
dfs(start)
return image

dfs(row, col):
  if out of bounds or image[row][col] is not oldColor:
    return
  image[row][col] = newColor
  dfs four neighbors

Reference Code

class Solution:
    def floodFill(self, image, sr, sc, color):
        old = image[sr][sc]
        if old == color:
            return image

        rows, cols = len(image), len(image[0])

        def dfs(r, c):
            if r < 0 or c < 0 or r == rows or c == cols or image[r][c] != old:
                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

Sample Dry Run

Step	State	Result
Start (1,1)	oldColor = 1	new color is 2
DFS region	Recolors connected 1s touching start	Top-left region becomes 2
Blocked cells	0s stop traversal	They remain 0
Separate 1	Bottom-right is not connected	It remains 1

Complexity

Measure	Value	Reason
Time	O(rows * cols)	In the worst case the connected region covers the whole image.
Space	O(rows * cols)	DFS recursion can include every cell in the connected region.

Edge Cases

If the new color equals the old color, return immediately.
Do not cross pixels with a different color.
Only four-direction neighbors count unless specified.

Interview Checklist

Save the original color before mutating.
Guard against same color to avoid repeated recursion.
Check bounds before reading a cell.

FAQs

Why check oldColor equals new color?

Without this guard, DFS can keep revisiting cells that still match the target color.

Is this a graph problem?

Yes. Each pixel is a node and four-direction neighbors are edges.

What is the core pattern?

Boundary-limited grid DFS.

Flood Fill: Boundary DFS Pattern