Number of Islands: Flood Fill as Component Counting

"Number of Islands" is a Medium-level staple in Amazon, Google, Bloomberg loops, and it is a textbook fit for the Tree DFS pattern — one of the nine patterns that cover the bulk of what FAANG coding interviews actually test. Part 10 of 11 in the Tree DFS arc.

The Problem

Given a grid of '1' (land) and '0' (water), count the islands — maximal 4-directionally connected land regions. By most published lists this is among the most-asked questions at Amazon, period. It is connected-components dressed as geography.

Input:  grid = [
    ["1", "1", "0", "0", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "1", "0", "0"],
    ["0", "0", "0", "1", "1"],
]
Output: 3

Recognizing the Tree DFS Pattern

Depth-first search commits to one branch before trying siblings — recursion (or an explicit stack) whose call structure mirrors the tree itself. Its natural questions are about paths (root to leaf), subtree properties (computed bottom-up from children), and exhaustive exploration (islands, connected regions). The recurring design decision is what each recursive call returns versus what it accumulates in shared state.

Count maximal connected regions equals: scan every cell; each unvisited land cell starts a new component; flood-fill (DFS) consumes the whole component so it is never counted again. The count lives in the outer scan, the consumption in the DFS — keeping those roles straight is the pattern.

The Approach

Iterate all cells. On finding land, increment the count and DFS-sink the entire island — overwrite '1' with '0' (or a visited mark) before recursing into the four neighbors. Sinking at visit time prevents revisits without a separate structure.

Recursion depth is the caveat to volunteer: a grid that is one giant island recurses O(m·n) deep, past Python's default limit near 1000 — the iterative stack (or BFS) version is the production answer, and saying so unprompted reads as experience.

Python Solution

def num_islands(grid: list[list[str]]) -> int:
    """Count 4-connected regions of '1'. Mutates grid (sinks islands)."""
    if not grid or not grid[0]:
        return 0
    rows, cols = len(grid), len(grid[0])

    def sink(r: int, c: int) -> None:
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != "1":
            return
        grid[r][c] = "0"                   # mark before recursing
        sink(r + 1, c)
        sink(r - 1, c)
        sink(r, c + 1)
        sink(r, c - 1)

    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                count += 1
                sink(r, c)
    return count

Complexity

• Time: O(m·n) — every cell is visited a constant number of times
• Space: O(m·n) — recursion depth in the worst case (one snake-shaped island)

Interview Tips and Follow-Ups

• Ask whether mutating the grid is acceptable before sinking it — if not, a visited set costs O(m·n) and nothing else changes.
• Union-Find also counts components and shines in the follow-up Number of Islands II (land added dynamically) — name the boundary between the tools.
• Escalations: Max Area of Island (return size), Island Perimeter (count edges), Number of Distinct Islands (canonicalize shapes) — one flood fill, many toppings.

More Tree DFS problems — and the other eight patterns — live in the Technical Interview category. Drill the pattern, not the problem: that is the entire thesis of this series.