What is the Flood Fill Algorithm?
Understand the flood fill algorithm, its DFS/BFS implementation, common pitfalls, and how to answer this interview question.
Expected Interview Answer
Flood fill is a traversal algorithm that starts at a given cell in a grid and recursively or iteratively spreads to all orthogonally (or optionally diagonally) connected cells sharing the starting cell's original color or value, replacing each with a new value, running in O(rows * cols) time in the worst case since every cell is visited at most once.
The algorithm is DFS or BFS applied to a grid, treating each cell as a graph node and connections to same-value neighbors as edges. Starting from the seed cell, it checks whether the current cell matches the target color before recoloring it and recursing (DFS) or enqueueing (BFS) into its unvisited same-colored neighbors; cells that are out of bounds, already recolored, or a different color are skipped. It underlies the paint-bucket tool in image editors, the number-of-islands and connected-component family of interview problems, and maze-solving. A subtle correctness trap is recoloring a cell to the exact same new value as an already-visited neighbor's replacement value, which can cause the recursion to think cells are still unvisited; the fix is to capture the original color before mutating, and to check equality against that captured original color throughout the traversal, or to use a separate visited set.
- O(rows * cols) time, since each cell is processed at most once
- Directly reusable for connected-component counting problems
- Works iteratively (BFS/stack) to avoid recursion depth limits
- Foundation of the paint-bucket tool in raster image editors
AI Mentor Explanation
Flood fill is like a groundskeeper repainting a patch of turf that has gone one uniform shade of yellow after a drought, starting from one dry spot and spreading the new green paint only to directly touching patches that are also that same yellow shade. The moment a neighboring patch is a different color, like already-green turf or the boundary rope, the spread stops there without crossing it. Each repainted patch is never revisited since its color has already changed to green, which naturally halts the spread once the whole yellow patch is covered. This is exactly why the entire connected dry patch gets repainted in one pass, without touching any unrelated part of the field.
Step-by-Step Explanation
Step 1
Capture the original value
Read the color/value at the starting cell before any mutation, so later comparisons stay correct.
Step 2
Check the current cell
If it is out of bounds, already changed, or does not match the original value, stop this branch.
Step 3
Recolor and recurse or enqueue
Set the cell to the new value, then recurse (DFS) or enqueue (BFS) into its orthogonal neighbors.
Step 4
Terminate on exhaustion
The fill stops naturally once every connected matching cell has been recolored and has no more unvisited matching neighbors.
What Interviewer Expects
- Explain the algorithm as DFS/BFS applied to a grid graph
- State O(rows * cols) time complexity clearly
- Identify the same-new-color trap and how capturing the original value fixes it
- Mention real applications: paint bucket tool, number of islands, maze solving
Common Mistakes
- Not capturing the original color before mutating, causing incorrect early termination
- Recoloring to the same value as an already-filled neighbor, breaking the visited check
- Using recursion on very large grids without considering stack overflow, forgetting an iterative alternative exists
- Allowing diagonal spread when the problem specifies orthogonal-only connectivity
Best Answer (HR Friendly)
“Flood fill starts at one cell and spreads outward to every directly connected cell that shares the same original value, replacing each one, similar to how a paint bucket tool works in an image editor. I implement it with DFS or BFS, and the key detail is capturing the original value first so the traversal correctly knows which cells still need to be filled.”
Code Example
def flood_fill(image, sr, sc, new_color):
rows, cols = len(image), len(image[0])
old_color = image[sr][sc]
if old_color == new_color:
return image
def fill(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return
if image[r][c] != old_color:
return
image[r][c] = new_color
fill(r + 1, c)
fill(r - 1, c)
fill(r, c + 1)
fill(r, c - 1)
fill(sr, sc)
return imageFollow-up Questions
- Why does flood fill fail if new_color equals old_color without an early check?
- How would you implement flood fill iteratively using a stack or queue to avoid recursion limits?
- How does flood fill relate to solving the number of islands problem?
- How would you extend flood fill to allow diagonal connectivity?
MCQ Practice
1. What must be captured before mutating any cell in flood fill?
Capturing the original value before mutation is required so subsequent comparisons correctly identify which cells still need filling.
2. What happens if new_color equals old_color and there is no early-exit check?
Without an early exit, every matching cell keeps matching after being "recolored" to the same value, breaking the visited-tracking logic.
3. What is the time complexity of flood fill on a grid with R rows and C columns?
Each cell is visited and processed at most once, giving O(R * C) time in the worst case.
Flash Cards
What is flood fill, algorithmically? — DFS or BFS traversal over a grid that recolors all connected cells sharing the starting value.
Why capture the original color before mutating? — So later cells can still be correctly compared against the pre-fill value, avoiding early termination bugs.
What real-world tool is powered by flood fill? — The paint bucket tool in raster image editors.
What is the time complexity of flood fill? — O(rows * cols), since each cell is processed at most once.