What is the Flood Fill pattern?

The Flood Fill is a common coding interview pattern in Depth First Search problems. It provides a structured approach to solving related algorithm challenges efficiently.

When should I use Flood Fill?

Use the Flood Fill pattern when you encounter problems matching its characteristics. Check the "When to Use" and "Clues" sections in the lesson for specific indicators.

Is Flood Fill asked in FAANG interviews?

Yes, Flood Fill is an essential pattern commonly tested in FAANG and top tech company technical interviews.

Browse Curriculum

Depth-First Search

Easy

Flood Fill

Implement the 'Paint Bucket' tool found in image editors.

10 min read

Solve on LeetCode

Examples

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 dfs for Up, Down, Left, Right.

Visualization

Step 1 / 1

Visualization data missing

Initializing...

Custom Input

Watch the color spread outward from the center.

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.