cf.completefrontend
GRAPHS · FOUNDATION

Flood fill

Starting from one cell of a grid, spread to every touching cell of the same color, like the paint bucket in a drawing app.

Time O(rows * cols)Space O(rows * cols)7 practice problemsStep-through picture

The idea

A grid, like the pixels of an image or the cells of a spreadsheet, is a graph in disguise. Each cell is a node, and each cell is connected to the cells directly above, below, left, and right of it.

Flood fill starts at one cell and finds every cell connected to it that has the same color. It's what the paint bucket tool does: click one pixel, and the whole same-colored region changes color.

It's a DFS or BFS on the grid. You keep a list of cells still to check (a stack here), change each one's color when you reach it, and add its four neighbors that still have the old color. Changing the color doubles as the "visited" mark, so no extra array is needed.

An everyday example

Spilled water on a tiled floor

Water spilled on one tile spreads to the tiles touching it, but only to tiles at the same level. A raised tile stops it. The water keeps spreading until every reachable tile at that level is wet. A tile that is already wet doesn't need to be wet again.

How the example maps to the code
In the exampleIn the code
The tile where the water landsThe start cell grid[row][col]
Tiles at the same levelCells equal to oldColor
A tile getting wetgrid[nr][nc] = newColor
Water about to spread from a tileA cell waiting on the stack
A raised tile or the edge of the roomA different color or a position outside the grid

From the slow way to flood fill

  1. The obvious way to fill a region: paint the start cell, then scan the whole grid again and again, painting any oldColor cell that touches a painted cell, until a full scan paints nothing. A long winding region may grow by only one cell per scan, so this can cost (rows * cols) scans of rows * cols cells each.
  2. Most of those scans look at cells that can't change. A cell can only become paintable at the moment one of its four neighbors is painted. So when you paint a cell, only its four neighbors are new candidates, and nothing else needs to be looked at.
  3. Keep those candidates in a to-do list. A stack is the simplest: push a cell when it is painted, and later pop it to check its four neighbors. Any neighbor that still has oldColor gets painted and pushed in turn.
  4. Painting doubles as the "already done" mark, because a painted cell no longer equals oldColor. That only holds if the two colors differ, so return early when they don't. That loop is flood fill.

How it works

  1. Read oldColor, the color of the start cell. If it already equals newColor, there is nothing to do.
  2. Paint the start cell with newColor and put it on the stack.
  3. While the stack has cells, pop one, [r, c].
  4. For each of the four directions [dr, dc], compute the neighbor nr = r + dr, nc = c + dc.
  5. Skip the neighbor if it is outside the grid or its color is not oldColor.
  6. Otherwise paint it with newColor and push it, so its own neighbors get checked later.
  7. When the stack is empty, the whole region has been painted.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function floodFill(grid, row, col, newColor) {
  2. const oldColor = grid[row][col];
  3. if (oldColor === newColor) return grid;
  4. const stack = [[row, col]];
  5. grid[row][col] = newColor;
  6. while (stack.length > 0) {
  7. const [r, c] = stack.pop();
  8. for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
  9. const nr = r + dr;
  10. const nc = c + dc;
  11. if (nr < 0 || nr >= grid.length || nc < 0 || nc >= grid[0].length) continue;
  12. if (grid[nr][nc] !== oldColor) continue;
  13. grid[nr][nc] = newColor;
  14. stack.push([nr, nc]);
  15. }
  16. }
  17. return grid;
  18. }

How fast it is

TimeO(rows * cols)
Extra memoryO(rows * cols)

Each cell is painted and pushed at most once, and each pop checks 4 neighbors. In the worst case the whole grid is one region and sits on the stack.

  • Best caseO(1)

    oldColor already equals newColor, or the start cell's four neighbors all have other colors. Only a few cells are checked.

  • Average caseO(k)

    k is the number of cells in the region. Each is pushed once and checks 4 neighbors, whatever the grid size.

  • Worst caseO(rows × cols)

    The whole grid has one color, so every cell is in the region.

Common mistakes

  • Forgetting the oldColor === newColor check. Painted cells still match, so the fill runs forever.
  • Checking grid[nr][nc] before the bounds check. Reading grid[-1] gives undefined, and reading a column of it crashes.
  • Painting a cell when it is popped instead of when it is pushed. The same cell can be pushed by several neighbors.
  • Using recursion on a huge region. A 1000 by 1000 canvas can overflow the call stack; an explicit stack array does not.

When to use it

Look for these clues in a problem:

  • The input is a grid of characters or numbers, like ["..#", ".##"].
  • The question asks about regions, shapes, islands, or areas of touching cells.
  • Cells connect up, down, left, and right (sometimes diagonally too).
  • You need to paint, count, measure, or remove a connected region.

Check yourself

Answer each one in your head first, then open it.

Why paint a cell when it is pushed, not when it is popped?

If you wait until the pop, two neighbors can both see the cell still has oldColor and both push it. Painting at the push makes the second neighbor see newColor and skip it.

How many times can one cell be pushed?

At most once. It is pushed only while it has oldColor, and it is painted in the same step, so it never matches again.

Does changing pop to taking from the front change which cells are painted?

No. It changes the order to rings around the start, but the same connected cells are painted either way.

In the trace, why is (1,2) popped before (0,1), even though (0,1) was found first?

Both were pushed by (1,1), with (1,2) pushed last. A stack hands back the newest item first, so the fill goes deep to the right before coming back.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 7 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The fill keeps one rule: every painted cell belongs to the region, meaning it had oldColor and connects to the start through cells that had oldColor. The start cell fits. A neighbor is painted only if it is next to a painted cell and still has oldColor, so it fits too.

It also misses nothing. Every painted cell is pushed once and later popped, and the pop checks all four of its neighbors. So when the stack is empty, no painted cell has an unpainted oldColor neighbor. Any region cell left unpainted would have a path from the start, and somewhere on that path an unpainted region cell would sit next to a painted one, which can't happen.

It always ends, because each push changes a cell from oldColor to newColor, and that can happen at most once per cell when the colors differ. The early return for oldColor === newColor is what makes that true: without it, a painted cell would still match and could be pushed forever.

Going deeper

3 more ideas

Why painting works as the visited mark

A cell is only pushed when it still has oldColor, and it is painted at the same moment. After that it no longer equals oldColor, so no neighbor can push it again. That's why the early return for oldColor === newColor matters: without it, painted cells would still look unvisited and the loop would never end.

How long it takes

Each cell is pushed at most once and checks 4 neighbors, so the work is about 4 * rows * cols, which is O(rows * cols). The stack can hold up to every cell in the region, so the extra memory is also O(rows * cols) in the worst case.

Counting regions and other variations

To count islands, loop over every cell; each time you find an unpainted land cell, add one to a counter and flood fill from it. For 8-way connection, add the four diagonal directions. If you must not change the input, keep a separate seen grid instead of painting.

Work it by hand

Every step in a table, with why

Fill the region of 5s that contains the cell at row 1, column 1 with the color 8. Two other 5s touch the region only at a corner.

grid = [[5, 5, 2, 5], [2, 5, 5, 2], [5, 2, 5, 5]], row = 1, col = 1, newColor = 8

StepPopped [r, c]Painted nowstack afterWhat happensWhy
1-(1,1)(1,1)oldColor = 5The start cell is 5, which differs from 8, so paint it and push it.
2(1,1)(0,1), (1,2)(0,1), (1,2)Two neighbors matchDown (2,1) is 2 and left (1,0) is 2. Up (0,1) and right (1,2) are 5, so both are painted and pushed.
3(1,2)(2,2)(0,1), (2,2)Go deeper to the rightpop takes the newest cell, (1,2). Only its down neighbor (2,2) is still 5; (1,1) is already 8.
4(2,2)(2,3)(0,1), (2,3)Keep goingDown is outside the grid. Up is painted. Right (2,3) is 5. Left (2,1) is 2.
5(2,3)none(0,1)Dead endDown and right are outside the grid, up (1,3) is 2, and left (2,2) is painted.
6(0,1)(0,0)(0,0)Back to the older cellDown (1,1) is painted, up is outside, right (0,2) is 2, and left (0,0) is 5.
7(0,0)noneemptyStopIts only in-grid neighbors are (1,0), which is 2, and (0,1), which is painted. The stack is empty.

The grid becomes [[8, 8, 2, 5], [2, 8, 8, 2], [5, 2, 8, 8]]: 6 cells painted, each pushed and popped once. The 5s at (0,3) and (2,0) stay, because they only touch the region at a corner, and corners don't count.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Flood fillO(rows × cols)O(rows × cols)You need to paint, measure, or remove one connected region of a grid.
Recursive flood fillO(rows × cols)O(rows × cols)The grid is small and you want the shortest code. A large region can overflow the call stack.
Union-find over all cellsO(rows × cols · α(n))O(rows × cols)You need to label every region at once, or cells keep changing and regions keep merging over time.

Extra memory: O(rows × cols) in the worst case, for the stack. It is often much less, because cells leave the stack as others join it.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Flood fill and the other approaches, on a scale where each line up is 10 times more steps.
  • Flood fill, Recursive flood fill, Union-find over all cells O(rows × cols)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Flood fill1001 million1 trillion
Recursive flood fill1001 million1 trillion
Union-find over all cells1001 million1 trillion

Inputs that need care

5 tricky inputs
newColor equals the start's color
Return the grid unchanged at once. Without this check the start cell would be pushed again by its own neighbor, and the loop would never end.
A 1 by 1 grid
The start is painted and pushed. Its pop finds all four neighbors outside the grid, and the fill ends after one cell.
Cells of the same color that touch only at corners
They are not filled, as (0,3) and (2,0) in the trace show. If the problem says diagonal cells connect, add the four diagonal directions.
An empty grid, or rows of different lengths
The code reads grid[row][col] and grid[0].length, so it expects at least one cell and equal-length rows. Check the input first if that isn't promised.
A 4000 by 4000 canvas filled with one color
That is 16 million cells, and each [r, c] pair is a small array. Store cells as one number, r * cols + c, in a typed array to save memory and time.

Variations and follow-ups

Twists interviewers add

Breadth-first fill

Take cells from the front with a head index instead of pop. It paints exactly the same cells, but in rings around the start, which also lets you record each cell's distance from the click.

Fill with a tolerance

Image editors often fill colors that are only close to oldColor. Then newColor might also count as close, so painting no longer works as the visited mark. Keep a separate seen grid of booleans.

Scanline fill

Paint a whole horizontal run of matching cells at once, then push only one cell for each new run found in the rows above and below. It pushes far fewer cells, which is why paint programs often use it.

Counting and measuring regions

Loop over every cell. Each time you find one that isn't painted yet, add one to a counter and fill from it, counting the cells it paints. That gives the number of islands and each island's area.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from a grid plus words like region, island, area, paint, or connected cells. The grid is a graph whose edges are the four directions.
  • Explain the mark out loud: "painting is my visited mark, so I paint when I push, and I return early if the colors are the same".
  • Test three tiny cases by hand: same color, a 1 by 1 grid, and two same-colored cells that touch only at a corner.
  • Expect "what if you can't change the input?": keep a separate seen grid. And "what about very large images?": use an explicit stack, not recursion, and store cells as single numbers.

Where frontend code uses it

The same idea in real UI code
  • The paint bucket tool in drawing apps and canvas editors fills a region of the ImageData pixel array this way.
  • The magic wand selection tool in image editors selects touching pixels of a similar color with the same spread.
  • Grid games built in the browser, such as Minesweeper, reveal a whole empty area with a flood fill when you click an empty cell.

Related algorithms