Flood Fill (Recursion)
DFS: recolor, then recurse into all 4 neighbors
This is graph traversal in disguise: each cell is a node, and same-colored neighbors are edges. Recursing outward from the start cell and recoloring as you go — while checking bounds and the original color at every step — naturally stops at any boundary where the color changes, without ever needing to track a separate 'visited' set (the recolor itself IS the visited marker).
Details
Animated on: image = [[1,1,1],[1,1,0],[1,0,1]], start=(1,1), newColor=2 — recolor the connected region (shown flattened row-major).
Problem:Flood Fill (Recursion)Easy
DFS: recolor, then recurse into all 4 neighbors
step 1 / 8
Start at (1,1), color=1. Recolor it and every 4-directionally connected cell that shares the same original color.
- start=4· arr[4] = 1
1FUNCTION floodFill(image, r, c, newColor):2 oldColor = image[r][c]3 FUNCTION dfs(r, c):4 IF (r,c) is out of bounds or image[r][c] != oldColor: RETURN5 image[r][c] = newColor6 dfs into the 4 neighbors: up, down, left, right7 call dfs(r, c)
← / → step · space play · Home restart
Every step in words
Show all 8 steps
- Start at (1,1), color=1. Recolor it and every 4-directionally connected cell that shares the same original color.
- (1,1) matched the original color 1 — recolor to 2, then visit its 4 neighbors.
- (0,1) matched the original color 1 — recolor to 2, then visit its 4 neighbors.
- (0,0) matched the original color 1 — recolor to 2, then visit its 4 neighbors.
- (1,0) matched the original color 1 — recolor to 2, then visit its 4 neighbors.
- (2,0) matched the original color 1 — recolor to 2, then visit its 4 neighbors.
- (0,2) matched the original color 1 — recolor to 2, then visit its 4 neighbors.
- Flood fill complete: [[2,2,2], [2,2,0], [2,0,1]].
Now solve it yourself
Watching is the first half. The second is writing it without the animation.