On this page
Description
A grid of cells, whether pixels, map tiles or land and water, is a graph in disguise. Each cell is a node, and its up, down, left and right neighbors are its edges. Nothing has to be built: the coordinates imply the edges. Filling a region, counting islands and finding enclosed areas are then ordinary graph traversals, with two concerns of their own: staying inside the grid, and marking cells as visited cheaply. This skill covers the fill, the island count, and the trick of flooding inward from the border.
We'll go from simple to more technical:
- The pattern: repaint, then spread to the four neighbors.
- A second flavor: flood from the border to find what's enclosed.
- Where flood fill runs in production (paint buckets, imaging, game maps).
- What breaks it: same colors, repainting late, bounds, and recursion depth.
The approach
Java
int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
int oldColor = image[sr][sc];
if (oldColor == newColor) return image; // nothing to repaint - and the guard below would never stop
fill(image, sr, sc, oldColor, newColor);
return image;
}
void fill(int[][] image, int r, int c, int oldColor, int newColor) {
if (r < 0 || r >= image.length || c < 0 || c >= image[0].length) return; // bounds first
if (image[r][c] != oldColor) return; // a different color - or already repainted
image[r][c] = newColor; // repaint BEFORE recursing: this is the visited mark
fill(image, r + 1, c, oldColor, newColor);
fill(image, r - 1, c, oldColor, newColor);
fill(image, r, c + 1, oldColor, newColor);
fill(image, r, c - 1, oldColor, newColor);
}
Python
def flood_fill(image: list[list[int]], sr: int, sc: int, new_color: int) -> list[list[int]]:
old_color = image[sr][sc]
if old_color == new_color:
return image # nothing to repaint - and the guard below would never stop
def fill(r: int, c: int) -> None:
if not (0 <= r < len(image) and 0 <= c < len(image[0])):
return # bounds first
if image[r][c] != old_color:
return # a different color - or already repainted
image[r][c] = new_color # repaint BEFORE recursing: this is the visited mark
fill(r + 1, c)
fill(r - 1, c)
fill(r, c + 1)
fill(r, c - 1)
fill(sr, sc)
return image
Repainting a cell before exploring its neighbors means that when a neighbor's recursion comes back to it, it no longer matches oldColor and is skipped - no separate visited array. That trick has two conditions: the repaint must happen before the recursive calls, and the new color must actually differ from the old one, which is why floodFill returns early when they're equal. Counting islands is the same fill used as a component counter: scan every cell, and each time you find unvisited land, count one island and flood it.
A second flavor: flood from the border
Some questions ask what can't escape: land cells that can't walk off the grid, regions fully surrounded by walls. Searching outward from every cell to see whether it reaches the edge repeats work. Reverse the question instead - flood from the border inward:
Java
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++)
if ((r == 0 || c == 0 || r == rows - 1 || c == cols - 1) && grid[r][c] == 1)
sink(grid, r, c); // flood everything reachable from this border cell
// whatever land is left can't reach the edge
Python
for r in range(rows):
for c in range(cols):
if (r == 0 or c == 0 or r == rows - 1 or c == cols - 1) and grid[r][c] == 1:
sink(grid, r, c) # flood everything reachable from this border cell
# whatever land is left can't reach the edge
Every cell connected to the border is reached from the border, so whatever the border floods can't mark is enclosed. It's one O(rows * cols) pass. All four edges count: flooding from the top and bottom rows alone misses land that only touches the left or right edge.
Where you'll see it
The paint-bucket tool in every image editor, region labeling in medical and satellite imaging (counting cells or lakes), "which tiles are reachable" in game maps, and connected regions in spreadsheets or CAD layouts are flood fills over a grid.
Which tool for which job?
| You need | Use |
|---|---|
| Repaint one connected region | flood fill from the starting cell |
| Count islands or regions | an outer scan plus one fill per new region |
| What can't reach the edge | flood from every border cell, count what's left |
| A big grid | an explicit stack or a queue, not recursion |
| Land added one cell at a time | union-find, merging with each land neighbor |
| The input must stay untouched | a separate visited array |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| New color equals old color | cells keep calling each other until the stack overflows | return early when they're equal |
| Repainting after the recursive calls | neighbors come straight back in | repaint first, then recurse |
| Reading the cell before checking bounds | an exception in Java; in Python -1 silently reads the last row | check bounds first |
| Recursion on a large grid | Java overflowed at 300 x 300 | an explicit stack or a queue |
| Mixing 4- and 8-direction rules | island counts disagree with the problem | use the rule the problem states |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. A flood fill is called with newColor equal to the starting cell's color. What happens without the early return?
Show answer
Infinite recursion, ending in a StackOverflowError. Repainting leaves the cell unchanged, so when a neighbor recurses back into it, it still matches the old color and is processed again - two cells keep calling each other. The fix is to return immediately when the colors are equal (there's nothing to do anyway).
2. Why is "flood from the border, then count what's left" better than checking each land cell for a path to the edge?
Show answer
Checking from every cell repeats the same search over and over - O((rows * cols)^2) in the worst case. Any cell that can reach the edge is also reachable from the edge, so one flood from all border cells marks every escapable cell in a single O(rows * cols) pass; the unmarked land is exactly what's enclosed.
3. How does counting islands use flood fill?
Show answer
Scan every cell; each time you meet land that hasn't been visited, count one island and flood-fill it (marking all its cells visited). Every island is flooded exactly once, from whichever of its cells the scan meets first - the grid version of counting connected components with an outer loop.
Key takeaways
- A grid is an implicit graph: cells are nodes, their 4 (or 8) neighbors are edges - check bounds before reading a cell.
- Repainting before recursing is the visited mark, and it only works if the new color differs from the old one.
- Counting islands is flood fill plus an outer loop: one fresh fill per island.
- For "what can't reach the edge" questions, flood from the border and count what's left - one pass.
- Recursion depth can reach rows * cols; use an explicit stack or a queue on large grids.