Depth-First Search
Easy
Flood Fill
Implement the 'Paint Bucket' tool found in image editors.
10 min read
Solve on LeetCodeExamples
Input:image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, newColor = 2
Output:[[2,2,2],[2,2,0],[2,0,1]]
Explain:
Start at pixel (1,1). All connected '1's become '2'.
Problem Understanding
You are given an m x n integer grid image representing a bitmap image. You are also given a starting pixel (sr, sc) and a newColor.
You need to perform a Flood Fill: change the color of the starting pixel and all 4-directionally connected pixels of the same color to newColor.
Think of the 'Bucket Fill' tool in Paint.
Algorithm Strategy
This is a standard DFS traversal on a grid.
- Check Color: If
image[sr][sc] == newColor, we don't need to do anything (avoid infinite loop). - Store Old Color: We only move to neighbors that match
oldColor. - DFS Function:
dfs(r, c)- Check Bounds: If out of bounds, return.
- Check Match: If
image[r][c] != oldColor, return. - Paint: Update
image[r][c] = newColor. - Recurse: Call
dfsfor Up, Down, Left, Right.
Visualization
Step 1 / 4
1
1
0
1
1
0
0
0
1
Start Flood Fill at (1,1). Target Color: 1, New Color: 2.
1x
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.