Pattern 3: DFS on a grid (flood fill)

Here the grid reveals its graph nature: neighboring cells are "connected". To explore an entire connected region, depth-first search (DFS) "floods" out from a cell, spreading to the neighbors — like the paint bucket of an image editor.

Tried it? Maybe you tried counting 1s or finding borders — and got lost in the cases. The theory below gives the right framework: each new island triggers a flood that marks all the connected land.

The theory: flood fill with DFS

Think of "filling with the paint bucket": from a cell, you spread to the neighbors of the same region, and from those neighbors to their neighbors, until the region runs out. That is DFS on a grid:

dfs(r, c):
    if (r,c) is outside the grid     → stop
    if (r,c) is not in the region,
       or was already visited        → stop
    mark (r,c) as visited
    dfs(r+1, c); dfs(r-1, c)         # the 4 neighbors
    dfs(r, c+1); dfs(r, c-1)

The first two lines are the base cases that stop the recursion (the grid's equivalent of "hitting the wall"). Marking as visited is what prevents going back and falling into an infinite loop.

For Number of Islands: walk the grid; every time you find land not yet visited, it is a new island (+1), and you trigger a DFS that sinks the entire island. Since the DFS marks everything that is connected, each island is counted exactly once. Watch the DFS flooding — the current cell highlighted, the blue showing what has already been visited:

Why is it O(m·n) time and O(m·n) space?

• Time: the outer loop goes through all the cells; the DFS visits each cell at most once in total (once marked, it is ignored). Adding up, each cell is processed a constant number of times → O(m·n).
• Space: the visited grid is O(m·n); and the recursion stack can reach O(m·n) in the worst case (an island that snakes through all the cells). You can save space by marking in the grid itself (sinking the land into water) instead of a separate grid.

Recursive DFS = implicit stack

Recursion uses the call stack to remember where to return — it is the same stack you saw in the String section, now working for you for free. You can write the same DFS iteratively with an explicit stack (stack), useful when the recursion gets too deep and overflows. Both forms explore in the same "go deep first" order.

Where DFS on a grid shows up

Counting/measuring connected regions (islands, maximum island area), filling regions (flood fill, capturing surrounded regions), and detecting shapes. Whenever the question is about "what is connected to what" in a grid, DFS (or BFS, from lesson 6) is the tool. And that is exactly the bridge to the Graphs section: the grid is just a graph with regular neighborhoods.

Summary

• A grid is a graph; flood fill with DFS explores an entire connected region.
• Base cases (outside the grid / not part of it / already visited) stop the recursion; marking visited avoids a loop.
• Number of Islands: +1 and a DFS for each new piece of land → each island counted once.
• O(m·n) time; O(m·n) space (visited + recursion stack).

Next lesson: when the path matters and can be undone — backtracking.