DSA Visualizer
GRID

Flood Fill

The paint bucket, one step at a time. Click any cell to fill from there, and switch between the queue and the call stack.

The paint bucket: from one cell, spread to every connected cell with the same value.

0
1
2
3
4
5
6
7
0
1
2
3
4
5
Queue
(2, 5)
Variablesold=2
Start at (2, 5). Its value is 2, so that is the value we spread from. Put it in the queue.
0
FilledFilled
12
LeftRemaining
1
QueueIn queue
1 / 26

Pseudocode

1old = grid[start]; queue = [start]
2while queue is not empty:
3 (r, c) = queue.pop_front()
4 fill (r, c)
5 for each neighbour (nr, nc) of (r, c):
6 if inside and grid[nr][nc] == old and not filled: queue.push((nr, nc))

Legend

Visiting nowIn the queueVisited

Grid

Click any cell to fill from there.

Want exact values? Edit this grid in the 2D Array Visualizer →

Tip: Space play/pause · ← → step

Learn flood fill

Flood fill is the paint-bucket tool. Starting from one cell, it spreads to every neighbour that has the same value, and from those to their neighbours, until the whole connected region is filled. BFS does it with a queue; DFS does it with recursion.

All three are the same idea in different clothes: a grid is a graph where every cell is joined to its four neighbours, and each algorithm walks that graph while remembering which cells it has already seen. Compare with number of islands and bfs shortest path.

Each cell is visited at most once and looks at four neighbours, so every one of them runs in O(rows · cols) time. The queue or call stack can grow to that size too.

How flood fill works

Pick the paint bucket, click inside a shape, and the whole shape changes colour but nothing outside it does. The tool has to answer one question for every pixel: is this pixel connected to where I clicked, through pixels of the same colour? Flood fill is that question turned into a loop.

Start from the clicked cell and remember its value. Look at its four neighbours. Any neighbour with the same value that has not been filled yet gets filled and becomes a new place to look from. Keep going until there is nowhere left to look. Cells with a different value act as walls, and so do the edges of the grid.

The only bookkeeping is a way to remember which cells still need their neighbours checked. Put them in a queue and you have breadth-first search: the fill spreads out in rings. Let recursion remember them on the call stack and you have depth-first search: the fill runs down one path as far as it can before backing up. Switch between the two above and watch the same region fill in two different orders.

The loop shape

BFS: queue = [start]. While the queue is not empty, take the front cell, fill it, and push every neighbour that is inside the grid, has the old value and is not filled yet. The check happens when a cell is pushed, so no cell enters the queue twice.

DFS: a function fill(r, c) that returns at once if the cell is outside the grid, has a different value or is already filled, and otherwise fills the cell and calls itself on the four neighbours. The call stack shown above is exactly the chain of cells the recursion is inside at that moment, and its depth is what can overflow on big regions.

A worked example: the region of 2s

The example grid has three values. Start at row 2, column 5, which holds a 2. BFS fills the twelve 2s that are connected to it and numbers them in the order they were taken from the queue. The 0s and 1s next to them are never touched, and neither are the two 2s in the top-right corner: they touch the region only at a corner, and corners do not count.

Twelve cells, twelve fills. Each fill also looked at four neighbours, so the work is a small constant times the region size.

Where you'll meet it

  • Image editors. The paint bucket, the magic-wand selection and the “remove background” tool are all flood fills, usually with a tolerance instead of an exact match.
  • Games. Revealing an empty area in Minesweeper, finding captured territory in Go, and clearing connected blocks in puzzle games.
  • Counting regions. Number of islands is a flood fill run from every unvisited land cell, with a counter.
  • Interviews. LeetCode 733, Flood Fill, is this exact function with a new colour as the value to write.

Mistakes beginners make

  • Comparing with the new value. Save the start cell's value first and compare neighbours with that saved value, not with whatever the start cell holds after you painted it.
  • Filling the same cell twice. Without a filled check, BFS pushes cells repeatedly and DFS never ends. Painting in place is the usual trick, which is why equal old and new colours need a guard.
  • Checking bounds after reading. Test that r and c are inside the grid before touching grid[r][c].
  • Trusting recursion on big inputs. A recursive fill on a large open region can overflow the call stack. Use the queue version, or an explicit stack, when the grid is big.

Next, run a fill from every patch of land and count them: Number of islands →

Flood fill questions

What is flood fill?

An algorithm that starts at one cell of a grid and spreads to every cell connected to it that has the same value, changing them all. It is what the paint bucket does in an image editor, and it is a plain graph search where each cell is joined to its four neighbours.

Should I use BFS or DFS for flood fill?

Both fill exactly the same cells, only in a different order. Recursive DFS is the shortest code. BFS with a queue is safer on large regions, because a recursive fill goes one call deeper for every cell in a long path and can overflow the stack: Python's default limit is 1000 calls, which a 32 × 32 open region already exceeds.

Why does LeetCode 733 fail when the new colour equals the old one?

Most solutions mark a cell as done by painting it the new colour, then keep spreading into neighbours that still have the old colour. If old and new are the same, a painted cell still looks unvisited, so the search loops forever. The fix is one line: if the colours are equal, return immediately. The visualizer keeps a separate filled set, so it never has that problem.

Does flood fill spread diagonally?

Not by default. The usual version is 4-connected: up, down, left, right. An 8-connected fill adds the four diagonals and can leak through gaps where two regions touch only at a corner, which is why paint tools use 4-connectivity.