Flood Fill
The paint-bucket tool, and the simplest possible introduction to traversing a grid as a graph
Problem Statement
Given a 2-D image of colours, a starting pixel, and a new colour, repaint the starting pixel and every pixel connected to it horizontally or vertically that shares its original colour.
This is the paint-bucket tool from any image editor.
Input: image = [[1,1,1],
[1,1,0],
[1,0,1]]
start = (1,1), new colour = 2
Output: [[2,2,2],
[2,2,0],
[2,0,1]]
The bottom-right 1 is NOT repainted — it only touches
the region diagonally, and diagonals do not connect.Intuition
A grid is a graph in disguise. Each pixel is a node, and each pixel is connected to the four pixels touching its edges.
(r-1, c)
│
(r, c-1) ─ (r,c) ─ (r, c+1)
│
(r+1, c)Once you see that, the problem is a standard traversal: start at one node, visit everything reachable, and change it on the way. There is no clever insight here — it is the plainest possible use of DFS, which is what makes it the right first grid problem.
The one thing to get right
Repaint a pixel the moment you arrive, not when you leave.
The new colour doubles as the visited marker. A repainted pixel no longer matches the original colour, so the check that decides whether to recurse also stops you revisiting anything.
Without that, A visits B, B looks back at A, and the two bounce forever — the cycle problem from the graphs page, in its simplest form.
Approach
Remember the original colour before changing anything
Once the first pixel is repainted, the colour you were matching against is gone.
Stop immediately if the new colour equals the old one
Otherwise nothing ever changes, the "already visited" test never fires, and the recursion runs forever. This is the only special case in the problem.
Visit: repaint, then recurse into four neighbours
Return early if the position is off the grid or does not hold the original colour.
Solution
def flood_fill(
image: list[list[int]], sr: int, sc: int, color: int
) -> list[list[int]]:
"""Repaint the connected region containing (sr, sc)."""
original = image[sr][sc]
# Without this, the "already painted" test never fires
# and the recursion never terminates.
if original == color:
return image
rows, cols = len(image), len(image[0])
def fill(r: int, c: int) -> None:
if not (0 <= r < rows and 0 <= c < cols):
return
if image[r][c] != original:
return
image[r][c] = color # paint on arrival — this is the visited mark
fill(r - 1, c)
fill(r + 1, c)
fill(r, c - 1)
fill(r, c + 1)
fill(sr, sc)
return image`original == color` is not an optimisation
It is a termination condition.
If the new colour matches the old, painting changes nothing. The check image[r][c] != original then never becomes true for a visited pixel, so A recurses into B and B recurses straight back into A.
The result is a stack overflow, and it only happens on the input where the correct answer is "do nothing".
Complexity Analysis
Time Complexity
O(rows × cols)
Space Complexity
O(rows × cols)
Time — each pixel is repainted at most once, and each does constant work checking four neighbours. Pixels outside the region are looked at but returned from immediately.
Space — the recursion stack. In the worst case the whole image is one region and the call chain is as long as the pixel count. Converting to an explicit stack or a BFS queue avoids the stack-overflow risk on very large images.
Edge Cases
Related Problems
- Number of Islands — the same fill, run repeatedly to count separate regions
- Rotting Oranges — a grid traversal where BFS is required rather than optional
- Graphs — why a visited marker is not optional