AlgoViz
HomeDepth-First Search

Flood Fill

Medium

Recolour the connected region

Problem

Given an image grid, a start pixel and a new color, flood-fill the connected region of the same color.

In simple words

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

The idea

From the start pixel, visit every 4-connected neighbour sharing the original colour and repaint it. Repainting as you arrive doubles as the visited mark — but only if the new colour differs from the old, which is the edge case to guard.

The trick

  • Return immediately when the new colour equals the original, or it loops forever.
  • Compare against the original colour, captured before you start painting.
  • O(rows × cols).
1
1
0
1
1
0
0
0
0
0
1
1

Step 1 of 8. Scan for land (1). Each new blob is one island — DFS sinks its whole region.

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

Depth-first sink.

1function sink(r, c) {2  if (oob(r,c) || grid[r][c] !== '1') return;3  grid[r][c] = '0';4  sink(r+1,c); sink(r-1,c); sink(r,c+1); sink(r,c-1);5}

Input

grid
3 × 4

Memory

at
—
cells marked
0

Output

islands
—

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.