Foundation drill for this topic
Easy DFS Recursive
In plain English: Starting from a pixel, change its color and all connected same-color pixels to a new color (like the paint bucket tool).
DFS from the starting pixel, changing color as you go. Only recurse into neighbors that match the original color — naturally stops at boundaries.
Prompt
Given a 2D image grid, a starting pixel (sr, sc), and a new color, flood fill the connected region of the starting pixel's color with the new color.
Try to write it from scratch before scrolling down.
Solution
def flood_fill(image, sr, sc, new_color):
orig = image[sr][sc]
if orig == new_color:
return image
m, n = len(image), len(image[0])
def dfs(i, j):
if i < 0 or i >= m or j < 0 or j >= n or image[i][j] != orig:
return
image[i][j] = new_color # fill
dfs(i+1, j); dfs(i-1, j); dfs(i, j+1); dfs(i, j-1)
dfs(sr, sc)
return image
# Test: flood_fill([[1,1,1],[1,1,0],[1,0,1]], 1, 1, 2)
# => [[2,2,2],[2,2,0],[2,0,1]]Quick recall drills to reinforce this pattern.
Recursive DFS on a grid with bounds + color check. Same pattern for island counting, connected regions, etc.
def fill(grid, i, j, old, new):
if i < 0 or i >= len(grid): return
if j < 0 or j >= len(grid[0]): return
if grid[i][j] != old: return
grid[i][j] = new
for di, dj in [(1,0),(-1,0),(0,1),(0,-1)]:
fill(grid, i+di, j+dj, old, new)