Flood Fill
Paint-bucket: recolor the connected region of same-colored pixels around (sr, sc).
02
Intuition
It's DFS/BFS on the grid: from the start pixel, spread to 4-neighbours sharing the original color, repainting as you go. Repainting doubles as the visited-marker.
03
Approach
1
Remember the original color
Only pixels matching it spread the fill; the new color is the paint.
2
DFS with bounds checks
Recurse on 4 neighbours inside the grid with the old color. Repaint before recursing to avoid revisits.
3
The self-fill trap
If newColor == oldColor the recursion never terminates — return immediately in that case.
04
Solution & live demo
python
▶1class Solution:
▶2 def floodFill(self, image, sr, sc, color):
▶3 old = image[sr][sc]
▶4 if old == color: return image
▶5 R, C = len(image), len(image[0])
▶6 def fill(r, c):
▶7 if 0 <= r < R and 0 <= c < C and image[r][c] == old:
▶8 image[r][c] = color
▶9 fill(r+1, c); fill(r-1, c); fill(r, c+1); fill(r, c-1)
▶10 fill(sr, sc)
▶11 return image
05
Edge cases
New color equals old color
Early return — otherwise infinite loop.
Start pixel isolated
Only it changes; neighbours differ in color.
06
Complexity
Time
O(R·C)
Space
O(R·C)
Each pixel painted once; recursion depth worst-case.