Flood Fill

algorithmintermediateTime O(cells)Space O(cells)

A grid is a graph where each cell touches its four neighbours. Flood fill is breadth-first search on it: a queue holds the frontier, each popped cell is painted and pushes the neighbours that still have the old colour. Painting on push keeps every cell from being queued twice. Counting islands is one fill per island.

Count the islands: groups of 1s connected up, down, left or right. Scan every cell. Each time a 1 is found that no fill has reached, that is a new island: count it and flood fill it to 2 so the rest of the scan skips it.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 8, with their answers.

Popped (0, 0). How many of its four neighbours join the queue?
- 2
- 3
- 1
Answer: 2. Only neighbours inside the grid that still have the old colour count, and painting them on push means none is queued twice.
Popped (1, 0). How many of its four neighbours join the queue?
- 0
- 1
- 4
Answer: 0. Only neighbours inside the grid that still have the old colour count, and painting them on push means none is queued twice.
Popped (0, 1). How many of its four neighbours join the queue?
- 0
- 1
- 4
Answer: 0. Only neighbours inside the grid that still have the old colour count, and painting them on push means none is queued twice.
Popped (1, 3). How many of its four neighbours join the queue?
- 2
- 3
- 1
Answer: 2. Only neighbours inside the grid that still have the old colour count, and painting them on push means none is queued twice.
Popped (2, 3). How many of its four neighbours join the queue?
- 0
- 1
- 4
Answer: 0. Only neighbours inside the grid that still have the old colour count, and painting them on push means none is queued twice.
Popped (1, 4). How many of its four neighbours join the queue?
- 0
- 1
- 4
Answer: 0. Only neighbours inside the grid that still have the old colour count, and painting them on push means none is queued twice.
Popped (3, 0). How many of its four neighbours join the queue?
- 0
- 1
- 4
Answer: 0. Only neighbours inside the grid that still have the old colour count, and painting them on push means none is queued twice.
Popped (3, 2). How many of its four neighbours join the queue?
- 0
- 1
- 4
Answer: 0. Only neighbours inside the grid that still have the old colour count, and painting them on push means none is queued twice.

How it runs, step by step

Count the islands: groups of 1s connected up, down, left or right. Scan every cell. Each time a 1 is found that no fill has reached, that is a new island: count it and flood fill it to 2 so the rest of the scan skips it.
Counting islands of 1s by flood filling each one as it is found.
(0, 0) is land no fill has touched: island 1. Flood fill from here so every cell of this island is sunk before the scan continues.
Island 1 starts at row 0 column 0.
Island 1. Pop (0, 0). 2 neighbours still land: (1, 0), (0, 1). Paint and queue them.
Cell 0, 0 is painted. 2 neighbours join the queue.
Island 1. Pop (1, 0). No unpainted neighbour with the old colour, so nothing joins the queue.
Cell 1, 0 is painted. 0 neighbours join the queue.
Island 1. Pop (0, 1). No unpainted neighbour with the old colour, so nothing joins the queue.
Cell 0, 1 is painted. 0 neighbours join the queue.
Island 1. The queue is empty: nothing reachable is left. 3 cells painted.
The queue is empty. 3 cells were painted.
(1, 3) is land no fill has touched: island 2. Flood fill from here so every cell of this island is sunk before the scan continues.
Island 2 starts at row 1 column 3.
Island 2. Pop (1, 3). 2 neighbours still land: (2, 3), (1, 4). Paint and queue them.
Cell 1, 3 is painted. 2 neighbours join the queue.
Island 2. Pop (2, 3). No unpainted neighbour with the old colour, so nothing joins the queue.
Cell 2, 3 is painted. 0 neighbours join the queue.
Island 2. Pop (1, 4). No unpainted neighbour with the old colour, so nothing joins the queue.
Cell 1, 4 is painted. 0 neighbours join the queue.
Island 2. The queue is empty: nothing reachable is left. 3 cells painted.
The queue is empty. 3 cells were painted.
(3, 0) is land no fill has touched: island 3. Flood fill from here so every cell of this island is sunk before the scan continues.
Island 3 starts at row 3 column 0.
Island 3. Pop (3, 0). No unpainted neighbour with the old colour, so nothing joins the queue.
Cell 3, 0 is painted. 0 neighbours join the queue.
Island 3. The queue is empty: nothing reachable is left. 1 cell painted.
The queue is empty. 1 cells were painted.
(3, 2) is land no fill has touched: island 4. Flood fill from here so every cell of this island is sunk before the scan continues.
Island 4 starts at row 3 column 2.
Island 4. Pop (3, 2). No unpainted neighbour with the old colour, so nothing joins the queue.
Cell 3, 2 is painted. 0 neighbours join the queue.
Island 4. The queue is empty: nothing reachable is left. 1 cell painted.
The queue is empty. 1 cells were painted.
4 islands. Every land cell was painted exactly once across all the fills, so the whole count is O(cells) even though it looks like a search inside a scan.
4 islands were counted.

Remember

Flood fill is BFS or DFS where the edges are same-coloured neighbours.
Mark a cell when it is pushed, not when it is popped, or it can be queued more than once.
Number of islands: scan every cell, and each unpainted land cell starts a new fill and a new count.

Topics covered

Where this is used

GraphicsPaint bucket and magic wand

GIMP's bucket fill and Photoshop's magic wand are this walk with the neighbour test loosened: a neighbour joins the region when its colour is within the tolerance setting of the pixel that was clicked, not only when it matches exactly. Comparing against the seed rather than against the previous cell is what stops a gentle gradient from carrying the fill across the whole picture. The bucket writes the new colour as it goes, while the wand keeps the visited cells as a selection mask instead of painting them, and the wand only walks the grid at all when its contiguous option is on. Raising tolerance widens the test, which is why one click can spill past a soft anti-aliased border into the region behind it.

Computer visionConnected-component labelling

Labelling every blob in a binary image is the count-islands loop: scan pixels, and each unlabelled foreground pixel starts a fill that stamps the whole blob with the next label. OCR uses it to cut a scanned line into separate glyphs before recognition, and microscopy uses it to count stained cells. The label a pixel ends up with is just the number of the fill that reached it.

GamesMinesweeper's cascade

Clicking a square with no adjacent mines opens a whole area at once, and that area is a flood fill seeded at the click. It spreads through squares whose mine count is zero and stops one square beyond them. The numbered squares are the frontier that failed the neighbour test, which is why the opened patch always comes ringed with numbers.

Electronics designFloating copper on a circuit board

When a PCB ground pour is filled, obstacles can split the copper into pieces that no longer reach any pad of that net: they look connected on screen but are electrically dead. A board tool such as KiCad separates the pour into connected islands and checks each one for a pad or via of the net, then drops the islands that have none. Same island count, with 'touches a pad' standing in for the colour test.

Why it works this way

Filling with the colour that is already there never stops

The guard for old == colour is not a shortcut, it is what keeps the loop finite. Painting is the only thing that marks a cell as visited here, so if the new colour equals the old one, painting changes nothing, every neighbour still matches old, and two adjacent cells push each other back and forth until memory runs out. Any fill that marks by overwriting needs this check; one that keeps a separate visited set does not.

Four neighbours or eight?

This is part of the problem statement, not an implementation detail. Count diagonals and two blobs that touch only at a corner become one region, so the island count drops. Grid puzzles and the classic island problems use four; connected-component labelling in image processing often uses eight so a thin diagonal stroke stays in one piece. Foreground and background cannot both use eight, or the picture contradicts itself: a closed diagonal loop would be one connected region and yet the background inside it would still be diagonally joined to the background outside, so the loop would enclose nothing. That is why the two are normally paired, eight for the foreground and four for the background.

The recursive version blows the stack

A four-way recursive fill is shorter to write, but its recursion depth is the size of the region. On a solid 1000 by 1000 area the recursion snakes down one column, back up the next and on across the grid, so it reaches a million cells deep before the first call returns, and the stack gives out. The explicit queue moves that memory to the heap, where a million entries is fine. Image editors go one step further with a scanline fill: paint a whole horizontal run at once and push only one seed per adjacent run, which cuts queue traffic by roughly the length of a run.

Counting islands destroys the grid

countIslands sinks each island by filling it with 2, which makes the visited test free: a land cell is unvisited exactly when it still reads 1. The price is that the caller's grid comes back overwritten, so either say so in the signature or fill a copy. A separate visited array costs one extra bit per cell and is the only option when the grid is read-only or shared.

Flood fillWikipedia
Pixel connectivity: 4-connected and 8-connected gridsWikipedia
Connected-component labelingWikipedia
Finding connected components in a graphcp-algorithms
Bucket Fill tool and its thresholdGIMP manual · docs.gimp.org