Number of Islands

This is the most common graph question in real interviews, and many candidates do not notice it is a graph question at all. The grid is the graph: each cell is a node, joined to the cells above, below, left and right. Once you say that out loud, the solution is the traversal template plus an outer loop.

The problem

You are given a grid of "1" (land) and "0" (water). An island is a group of land cells joined up, down, left or right — diagonal contact does not count. Return the number of islands. Everything outside the grid is water.

Example 1.

1 1 0 01 1 0 00 0 1 00 0 0 1

Output: 3. The top-left 2 × 2 block is one island. The cells at (2, 2) and (3, 3) touch only at a corner, so each is an island of its own.

Example 2.

1 1 0 1 11 0 0 0 10 0 1 0 1

Output: 3: the three cells in the top-left corner, the five cells along the right side, and the single cell in the middle of the bottom row.

Constraints. The grid is 1 to 300 rows and 1 to 300 columns.

Clarifying questions

• Do diagonal neighbours join islands? No, only the four directions.
• May I modify the grid? Ask. If yes, you can mark visited land by turning it into water, and save a visited set. Here, assume yes.
• Are the cells strings or numbers? Strings "1" and "0".
• Can the grid be empty? Assume at least one cell, but return 0 for an empty grid.

Approach 1: the simple way

Each island should be counted once, so give it a single representative: its first cell in reading order (top to bottom, left to right). For every land cell, flood-fill its whole island with a fresh visited set, and count the cell only if it is the smallest cell of that island.

1def flood(grid: list[list[str]], r: int, c: int) -> set[tuple[int, int]]:2    """All land cells connected to (r, c), using a fresh visited set."""3    rows, cols = len(grid), len(grid[0])4    seen = {(r, c)}5    stack = [(r, c)]6    while stack:7        cr, cc = stack.pop()8        for nr, nc in grid_neighbours(rows, cols, cr, cc):9            if grid[nr][nc] == "1" and (nr, nc) not in seen:10                seen.add((nr, nc))11                stack.append((nr, nc))12    return seen131415def num_islands_brute(grid: list[list[str]]) -> int:16    """Flood from every land cell; count it only if it is its island's first cell."""17    count = 018    for r in range(len(grid)):19        for c in range(len(grid[0])):20            if grid[r][c] == "1" and min(flood(grid, r, c)) == (r, c):21                count += 122    return count

(grid_neighbours is the helper from the core-idea lesson.) It is correct: every island has exactly one smallest cell. But each land cell floods its entire island. If the grid is one big island of m × n cells, every one of those cells floods all m × n cells: O((m × n)²). For a 300 × 300 grid that is 90,000 × 90,000 ≈ 8 × 10^9 steps. The waste is plain: after flooding an island once, you already know every cell in it, and then you flood it again from each of them.

The key insight

Flooding an island from any one of its cells reaches all of it. So the first time you meet an unvisited land cell, you have found a new island — count it, and flood it once, marking every cell visited. Every later cell of that island is already marked, so the outer scan skips it. Each cell is then flooded at most once, in total, across the whole grid.

This is count_components from the core-idea lesson: the outer loop over all nodes, and one traversal per unvisited node. The only difference is that the neighbours are computed from the row and column instead of read from a list.

Approach 2: one flood per island

1DIRECTIONS = ((-1, 0), (1, 0), (0, -1), (0, 1))234def num_islands(grid: list[list[str]]) -> int:5    """Count islands, sinking each one as it is found. Modifies grid."""6    if not grid:7        return 08    rows, cols = len(grid), len(grid[0])9    count = 010    for r in range(rows):11        for c in range(cols):12            if grid[r][c] != "1":13                continue14            count += 1                           # a new island starts here15            grid[r][c] = "0"16            stack = [(r, c)]17            while stack:18                cr, cc = stack.pop()19                for dr, dc in DIRECTIONS:20                    nr, nc = cr + dr, cc + dc21                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "1":22                        grid[nr][nc] = "0"       # sink when pushed23                        stack.append((nr, nc))24    return count

Step by step:

1. Scan every cell in reading order.
2. A "1" that is still land has not been reached by any earlier flood, so it starts a new island: add 1.
3. Sink it — turn it to "0" — and push it. Sinking is the visited mark, and it happens on push, so no cell is pushed twice.
4. Pop cells, and for each in-bounds neighbour that is still land, sink it and push it. When the stack is empty, the whole island is water.

Dry run on Example 1:

Result: 3. Cell (3, 3) is diagonal to (2, 2), but diagonals are not in DIRECTIONS, so the flood from (2, 2) never reaches it.

Complexity. Time O(m × n): the scan visits each cell once, and each land cell is pushed and popped at most once across all floods, checking 4 neighbours each time. Space O(m × n) in the worst case, for the stack when the whole grid is land. For a 300 × 300 grid that is about 360,000 neighbour checks instead of 8 × 10^9.

Approach 3: without modifying the grid, or with Union-Find

If the interviewer says the grid must not change, keep a visited set of (row, col) pairs, or a boolean grid of the same size. The time stays O(m × n); the space is now always O(m × n), not just in the worst case.

Union-Find is the other standard answer. Start with every land cell as its own group, and the count equal to the number of land cells. For each land cell, try to join it with the land cell to its right and the one below; each successful join merges two islands, so subtract 1. It costs O(m × n × α(m × n)) — effectively linear — and it shines when land is added over time, a follow-up below. The Redundant Connection lesson builds Union-Find properly.

Edge cases

• All water → 0; the flood never starts.
• All land → 1; one flood sinks everything, and the stack grows to hold a large part of the grid. This is why the iterative version matters: a recursive flood would go up to 90,000 frames deep and crash Python.
• One row or one column → the bounds check handles the missing neighbours.
• Corner-touching cells → separate islands, as in Example 1.

Follow-ups

• "Return the size of the largest island." Count the cells popped during each flood and keep the maximum. Same O(m × n).
• "Which cells can drain to both the top-left edges and the bottom-right edges?" (water flows to equal or lower neighbours). Do not flood from every cell. Flood uphill from each edge — two traversals — and return the cells both reached. O(m × n) instead of O((m × n)²).
• "Land is added one cell at a time; report the count after each addition." Re-flooding after every addition is O(k × m × n). Use Union-Find: each new cell adds 1, and each successful union with a land neighbour subtracts 1.