#733
Flood Fill
Easy Grid DFS
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Starting from one pixel, repaint it and every 4-directionally connected pixel of the same original colour with a new colour.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: paint a region of same-coloured pixels.
Why this works: DFS from the start to neighbours with the original colour; painting also marks them visited.
Example: [[1,1,1],[1,1,0],[1,0,1]], start (1,1), colour 2
all 1s connected to the centre become 2the bottom-right 1 isn't connected → stays 1
✦Hints open one at a time
DFS from the start cell to neighbours with the original colour.
If the new colour equals the original, return immediately — otherwise you loop forever.
↗Approach
Remember the original colour; recursively recolour matching neighbours. The recolouring itself marks cells as visited.
</>Solution (Java)
class Solution {
public int[][] floodFill(int[][] image, int sr, int sc, int color) {
int old = image[sr][sc];
if (old != color) fill(image, sr, sc, old, color);
return image;
}
private void fill(int[][] img, int r, int c, int old, int color) {
if (r < 0 || c < 0 || r >= img.length || c >= img[0].length || img[r][c] != old) return;
img[r][c] = color; // also marks visited
fill(img, r + 1, c, old, color);
fill(img, r - 1, c, old, color);
fill(img, r, c + 1, old, color);
fill(img, r, c - 1, old, color);
}
}!Common mistake
Missing the "same colour" early return, which causes infinite recursion.
Complexity
- Time: O(m·n).
- Space: O(m·n) recursion in the worst case.
Topic: Graphs
🎬 Episodes 74–85: video coming soon