DSA Tracker

Visualize

Flood Fill

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

time O(rows * cols)space O(rows * cols) recursion stack

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.

Details

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.

Problem:Flood FillEasy

Pattern:Graph BFS and DFS

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

step 1 / 8

Pixels of color 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

Every step in words

Show all 8 steps
  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.
  2. Start at (1,1), color 1. Recolor it first, then spread outward to every same-color neighbor.
  3. (0,1) still holds color 1, reached by going up from the pixel before it — recolor it to 2 and try its 4 neighbors next.
  4. (0,0) still holds color 1, reached by going left from the pixel before it — recolor it to 2 and try its 4 neighbors next.
  5. (1,0) still holds color 1, reached by going down from the pixel before it — recolor it to 2 and try its 4 neighbors next.
  6. (2,0) still holds color 1, reached by going down from the pixel before it — recolor it to 2 and try its 4 neighbors next.
  7. (0,2) still holds color 1, reached by going right from the pixel before it — recolor it to 2 and try its 4 neighbors next.
  8. Recoloring is done: 6 pixels changed to 2 — [[2,2,2], [2,2,0], [2,0,1]]. Cell (2,2) is still 1: nothing in the graph ever connected it to the start, so DFS never reached it.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Flood Fill in the editorAll Graph problemsBack to roadmap