Flood Fill
Problem Statement
You are given an image represented by an m x n integer grid, plus a starting pixel (sr, sc) and a new color.
Perform a flood fill: starting from (sr, sc), change the color of that pixel and every pixel connected to it 4-directionally that shares the original color of the starting pixel. Return the modified image.
This is exactly how the paint-bucket tool works in an image editor.
Input
A 2D int grid image, start coordinates sr and sc, and the target color.
Output
The same grid after the fill has been applied in place.
Constraints
- •
m == image.length - •
n == image[i].length - •
1 <= m, n <= 50 - •
0 <= image[i][j], color < 2^16 - •
0 <= sr < m, 0 <= sc < n
Examples
Example 1
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]]Example 2
image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0
[[0,0,0],[0,0,0]]Learning Objectives
- Apply single-source grid traversal (no outer scan — the start pixel is given).
- Recognise and handle the base case where the new color equals the original color.
- Practise the exact same DFS skeleton used for connected components.
Intuition
Flood fill is Number of Islands with the outer loop removed: you are handed the exact starting cell, so you traverse one region and recolor it. From the start pixel you spread to any neighbour that still holds the original color, then to that neighbour's neighbours, and so on.
The one subtlety is the stop condition. If the requested color is the same as the pixel's current color, filling would repaint cells to a color they already have, and a naive DFS would revisit them forever. Detecting that up front (and returning immediately) is the whole trick.
Common mistakes
- ×Infinite recursion when color equals the starting color — always short-circuit that case first.
- ×Comparing against the new color instead of capturing the original color before you start mutating.
- ×Reading the starting color after the first pixel has already been recolored.
Algorithm Explanation
- Record startColor = image[sr][sc].
- If startColor already equals the target color, return immediately (nothing to do, and this prevents an infinite loop).
- Otherwise DFS/BFS from (sr, sc): whenever a cell equals startColor, repaint it to the new color and recurse into its four neighbours.
- The bounds/color check is the base case that ends each branch.
Solutions
Solution: DFS (recursive fill)
Capture the original color, guard the no-op case, then recursively repaint every same-colored 4-directional neighbour.
Step-by-step
- startColor holds the region's color before any change.
- The early return handles startColor == color.
- fill repaints the current cell and recurses; the guard (out of bounds OR not startColor) stops each branch. Because a repainted cell no longer equals startColor, the traversal never loops back onto it.
O(m · n)
O(m · n)
Each pixel is repainted at most once; recursion depth is bounded by the region size.
Java implementation
Dry Run
Sample input
image = [[1,1,1],[1,1,0],[1,0,1]], start = (1,1), color = 2. startColor = 1.
| Call | Cell | image[cell] | Action |
|---|---|---|---|
| fill(1,1) | (1,1) | 1 | Paint to 2, recurse 4 dirs |
| fill(2,1) | (2,1) | 0 | Not startColor, return |
| fill(0,1) | (0,1) | 1 | Paint to 2, recurse |
| fill(0,0) | (0,0) | 1 | Paint to 2 |
| fill(0,2) | (0,2) | 1 | Paint to 2 |
| fill(1,0) | (1,0) | 1 | Paint to 2 |
| fill(2,0) | (2,0) | 1 | Paint to 2 |
| fill(1,2) | (1,2) | 0 | Not startColor, return |
All 1s connected to the center are repainted to 2. The 0s block the spread, and the isolated bottom-right 1 is never reached. Result: [[2,2,2],[2,2,0],[2,0,1]].
Interview Tips
This is a warm-up, so nail the edge case: state out loud that startColor == color must return early, and explain why (otherwise the fill revisits cells endlessly). Mention that BFS with a queue is an equally valid iterative version if they prefer no recursion. Interviewers often follow up by asking how flood fill relates to connected-components counting — the answer is that it is the inner traversal without the outer seeding loop.
Likely follow-ups
- Convert to an iterative BFS using a queue.
- Support 8-directional filling.
- Count how many pixels were changed.
Similar Problems
Key Takeaways
- Single-source fill = grid DFS/BFS without the outer seeding loop.
- Always capture the original color before mutating anything.
- Guard the no-op case (new color == old color) to avoid infinite loops.