Flood Fill
Implement the 'Paint Bucket' tool found in image editors.
Examples
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 color.
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 color.
Think of the 'Bucket Fill' tool in Paint.
Algorithm Strategy
This is a standard DFS traversal on a grid.
- Check Color: Remember
original = image[sr][sc]. If it already equalscolor, return the image — painting would change nothing and the recursion would never stop. - DFS Function:
dfs(r, c)- Check Bounds: If
(r, c)is outside the image, return. - Check Match: If
image[r][c] != original, return. This also stops at pixels already painted. - Paint: Set
image[r][c] = color. - Recurse: Call
dfsdown, up, right, then left.
- Check Bounds: If
Visualization
Paint from the start pixel. Every call is its own step, in the order the code makes them — down, up, right, left — with an arrow to the pixel about to be tried. A call that leaves the image lands on an empty cell outside it, and a call on a different colour, or on a pixel already painted, returns straight away.
Dry Run
Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2. So original = 1.
| Step | Call | Pixel | Action |
|---|---|---|---|
| 1 | dfs(1,1) |
1 | Paint 2. Call down. |
| 2 | dfs(2,1) |
0 | Not 1 — return. Back in (1,1): call up. |
| 3 | dfs(0,1) |
1 | Paint 2. Down (1,1) is already 2 and up (-1,1) is outside — both return. Call right. |
| 4 | dfs(0,2) |
1 | Paint 2. Down (1,2) is 0, up and right are outside, left (0,1) is already 2 — all return. Back in (0,1): call left. |
| 5 | dfs(0,0) |
1 | Paint 2. Call down. |
| 6 | dfs(1,0) |
1 | Paint 2. Call down. |
| 7 | dfs(2,0) |
1 | Paint 2. Down is outside, up (1,0) is already 2, right (2,1) is 0, left is outside — all return. |
| 8 | back in dfs(1,0) |
— | Up (0,0) and right (1,1) are already 2, left is outside — return. |
| 9 | back in dfs(0,0) |
— | Up and left are outside, right (0,1) is already 2 — return. dfs(0,1) is done too. |
| 10 | back in dfs(1,1) |
— | Right (1,2) is 0, left (1,0) is already 2 — return. |
Result: [[2,2,2],[2,2,0],[2,0,1]]. The bottom-right 1 is never reached: it touches the region only diagonally.
Edge Cases & Common Mistakes
- Same Color: If
color == original, painting changes nothing, so without the early return the recursion would never stop. Check this before the first call. - Out of Bounds: Check
randcbefore readingimage[r][c]. - Diagonals: Only the four side neighbours count. A pixel of the same colour touching only at a corner is not filled.
- Deep Recursion: A 50 by 50 image of one colour can recurse 2,500 calls deep. That is fine on LeetCode; for larger images use an explicit stack.
Solution
Recursive DFS. The four calls run down, up, right, then left — the order the figure and the dry run follow.
Flood Fill Code
1var floodFill = function(image, sr, sc, color) {2 const original = image[sr][sc];3 if (original === color) {4 return image;5 }6 const rows = image.length, cols = image[0].length;78 function dfs(r, c) {9 if (r < 0 || r >= rows || c < 0 || c >= cols) {10 return;11 }12 if (image[r][c] !== original) {13 return;14 }15 image[r][c] = color;16 dfs(r + 1, c);17 dfs(r - 1, c);18 dfs(r, c + 1);19 dfs(r, c - 1);20 }2122 dfs(sr, sc);23 return image;24};