Grid Flood Fill · bigonotes

A grid is a graph in disguise: every cell is a node and its up, down, left and right cells are its neighbors. Flood fill starts a DFS (or BFS) from one land cell and spreads to every connected land cell, which marks out one island. Islands, regions, farmland and "surrounded" puzzles are all this one move plus a little bookkeeping.

The idea#

Loop over every cell. When you find a land cell that no earlier flood has reached, start a flood from it: that is a new island. The flood marks every cell it touches, so later loop iterations skip them.

The flood itself is a plain DFS over neighbors. Two checks guard every step of it:

Bounds: 0 <= r < rows and 0 <= c < cols.
Eligibility: the cell is land and not visited yet.

You can track visited cells in a set of (r, c) tuples, or overwrite the grid in place (for example set land to 0) if you are allowed to change the input.

Why it's O(MN), not O((MN)²)#

The DFS call sits inside two nested loops, so it can look multiplicative. It isn't, because of single ownership: once a flood processes a cell, that cell is consumed and no other flood will ever process it again.

To see why, follow one land cell through the whole run:

Step	What happens	Cost
The loop reaches it	Checks `(r, c) not in visited`	1 op
A flood consumes it	Added to the island, marked visited	1 op
Post-processing	Copied into a tuple, checked against another grid, etc.	1 op
Ever after	Every loop or flood that reaches it skips it at once	$O(1)$ each

Add it up over the whole grid: $MN$ loop checks, at most $MN$ flood visits in total, and at most $MN$ copies. That is $O(3MN) = O(MN)$ .

It would be $O((MN)^2)$ if you removed the visited check, so that every cell started a fresh full flood and copied the whole island again. The rule to remember: work multiplies when the inner work is repeated for every step of the outer loop, and it adds when the work is shared out across the steps.

How to spot it#

Flood fill is the tool whenever a 2D grid has "connected" regions you need to count, measure, compare or relabel.

Keywords: island, region, area, connected, flood, enclosed, surrounded.
4-directional neighbors unless the problem says diagonals count.
Grid up to about $300 \times 300$ : one $O(MN)$ pass is the expected answer.

Template#

The loop finds each new island, and the flood consumes it. Add your bookkeeping (area, cells, corners) inside the flood.

seen = empty set
count = 0
flood(r, c):
    if (r, c) is off the grid: return          # bounds first
    if cell is not land or (r, c) in seen: return
    add (r, c) to seen
    for each of the 4 neighbors:
        flood(neighbor)
for each cell (r, c) in the grid:
    if cell is land and (r, c) not in seen:
        flood(r, c)                            # a new island
        count += 1
return count

Pitfalls#

These are the mistakes that most often cost a correct answer.

Forgetting the bounds check, or doing it after indexing the grid.
Comparing islands pairwise instead of hashing a key for each one. With $I$ islands that is $O(I^2)$ comparisons, and $I$ can be about $MN/2$ .
Sorting cells afterward to find something you could track during the flood.
Deep recursion on a large all-land grid can hit Python's recursion limit; an explicit stack or BFS avoids it.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first two.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Number of Islands

This is the template as it stands. Each flood started from the outer loop is one island.

Hint: Max Area of Island

Make the flood return the number of cells it consumed. Keep the largest return value.

Hint: Number of Distinct Islands

Record each cell relative to the island's first cell, (r - r0, c - c0), where (r0, c0) is the cell the loop met first. Two islands with the same shape then give the same key wherever they sit. Store each key as a tuple in a set, so a lookup is $O(1)$ and the total stays $O(MN)$ .

Hint: Count Sub-Islands

Flood each island in grid2, and check that every one of its cells is also land in grid1. Each cell is flooded once and checked once, so it is still $O(MN)$ .

Hint: Find All Groups of Farmland

Each group is a rectangle, and you need its top-left and bottom-right corners. Sorting the cells costs $O(MN \log MN)$ . The loop already meets the top-left corner first; keep a running max_r and max_c during the flood (with nonlocal) for the bottom-right corner.

Hint: Surrounded Regions

Flip the question. Any O connected to the border can't be captured, so flood from every border O and mark what you reach. Then flip every O that was not reached to X. The border has only $O(M + N)$ cells, so walk the first and last rows and columns instead of the whole grid, and watch for corners and grids that are one row or column wide.

Hint: Island Perimeter

No flood is needed. Every land cell gives 4 edges, minus one for each side it shares with another land cell.

Hint: Pacific Atlantic Water Flow

Flip the direction: flood uphill from each ocean's border cells instead of downhill from every cell. Run one search per ocean. The answer is the set of cells both searches reach.

Hint: Flood Fill

DFS or BFS from the start cell, recoloring every connected cell that has the original color. Return right away if the new color equals the original one, or the search never stops.

Key takeaways#

A grid cell is a node; its 4 neighbors are its edges.
A visited cell is consumed once, so loops plus floods plus copies add up to $O(MN)$ .
Hash a normalized shape (relative to the origin) instead of comparing islands pairwise.
When "inside" is hard to test, flood from the outside (the border) instead.
Track what you need during the flood rather than sorting afterward.

Core idea#

A grid is a graph: each cell is a node and its 4 neighbors are its edges. Flood fill spreads from one land cell to every connected land cell, which marks one island.

Key points#

Loop over every cell. An unvisited land cell starts a new flood, so a new island.
Guard every step with a bounds check and an eligibility check (land, not visited).
Track visited in a set of (r, c), or overwrite the grid if you may change it.
Nested loops plus DFS cost $O(MN)$ . Each cell is consumed once and skipped after that.
Distinct shapes: record cells relative to the first cell, and store the tuple in a set.
Surrounded Regions: flood from every border O. Flip each O the flood never reached.
Groups of Farmland: track max_r and max_c during the flood instead of sorting.
Island Perimeter needs no flood: 4 per land cell, minus one per shared side.

Template#

seen = empty set; count = 0
flood(r, c):
    if (r, c) is off the grid: return          # bounds first
    if cell is not land or (r, c) in seen: return
    add (r, c) to seen
    for each of the 4 neighbors: flood(neighbor)
for each cell (r, c) in the grid:
    if cell is land and (r, c) not in seen:
        flood(r, c)
        count += 1
return count

Pitfalls#

Indexing the grid before the bounds check.
Comparing islands pairwise. That is $O(I^2)$ for I islands and can reach $O((MN)^2)$ .
Normalizing a shape against an arbitrary cell instead of the first cell the loop meets.
Deep recursion on a large all-land grid. Use an explicit stack or BFS.

Say it in an interview#

"Each cell is visited once, so the loops and floods add up to O(MN)."
"When inside is hard to test, flood from the border instead."