Pattern visualizer

Flood Fill

Treat same-colored pixels as a graph: each pixel of the start pixel's color is a vertex, and two such pixels that touch 4-directionally share an edge. Flood fill is then just 'recolor every vertex reachable from the start' — ordinary graph traversal, not a scan of the whole image. That framing also explains the one trap in this problem: pixel (2,2) has the same starting color but no edge back to (1,1), so it is graph-unreachable and must stay untouched, even though a naive 'replace every pixel of this color' would have recolored it too. Animated on: image = [[1,1,1],[1,1,0],[1,0,1]], start=(1,1), newColor=2 — recolor the start pixel and every 4-directionally connected pixel that shares its original color..

DFS over same-color pixels — a grid is a graph in disguise

time O(rows * cols)space O(rows * cols) recursion stackstep 1 / 8

Pixels of color 1

0,0

0,1

0,2

1,0

1,1

2,0

2,2

line 1

Only the 7 pixels that already share the start pixel's color 1 are vertices, joined by an edge wherever two of them touch 4-directionally. Pixel (2,2) also has color 1 but has no edge back to the start — flood fill recolors a connected REGION, not every pixel of a given color, so it will stay untouched.

Pseudocode

1FUNCTION floodFill(image, sr, sc, newColor):
2  oldColor <- image[sr][sc]
3  IF oldColor = newColor RETURN image
4  FUNCTION dfs(r, c):
5    IF r < 0 OR r >= ROWS OR c < 0 OR c >= COLS RETURN
6    IF image[r][c] != oldColor RETURN
7    image[r][c] <- newColor
8    dfs(r - 1, c)
9    dfs(r + 1, c)
10    dfs(r, c - 1)
11    dfs(r, c + 1)
12  dfs(sr, sc)
13  RETURN image

← / → step · space play · Home restart

Where to practice Graph

Practice Graph problems All Graph problems Back to roadmap