AlgoViz
HomeGraphs

Flood fill algorithm

Medium

Repaint the connected region

Problem

Flood-fill a region of a grid starting from a pixel, replacing its color.

In simple words

From the start cell, spread to same-colour neighbours, repainting them — like a paint bucket.

The idea

Traverse from the start pixel to every 4-connected neighbour holding the original colour, repainting as you arrive. The repaint doubles as the visited mark, provided the new colour actually differs from the old one.

The trick

  • Return immediately when the new colour equals the original, or it never terminates.
  • Compare against the colour captured before painting began.
1
1
0
0
1
0
0
1
0
0
1
1
0
0
0
1

Step 1 of 9. Scan for land. Each unvisited '1' starts a new island; flood-fill its whole blob so it isn't counted twice.

1/9
Optimal
timeO(rows·cols)spaceO(rows·cols)

Sink each island you find.

1for (r, c) if (grid[r][c] === '1') {2  islands++;3  sink(r, c); // DFS marks the blob as water4}5function sink(r, c) {6  if (out of bounds || grid[r][c] !== '1') return;7  grid[r][c] = '0';8  for (const [dr, dc] of DIRS) sink(r+dr, c+dc);9}

Input

grid
4 × 4

Memory

at
—
cells marked
0

Output

islands
—
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
image = [[1,1,1],[1,1,0],[1,0,1]], sr=1, sc=1, color=2
Output:
[[2, 2, 2], [2, 2, 0], [2, 0, 1]]
Explanation:
The connected 1-region turns into 2s.

Example 2

Input:
image = [[0,0],[0,0]], sr=0, sc=0, color=2
Output:
[[2, 2], [2, 2]]
Explanation:
All connected 0s become 2.

Example 3

Input:
image = [[1]], sr=0, sc=0, color=1
Output:
[[1]]
Explanation:
Same colour → unchanged.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.