Number of Islands — Solution

Problem

Given a 2D grid of '1's (land) and '0's (water), count how many distinct islands exist. An island is a group of land cells connected horizontally or vertically, surrounded on all sides by water or the grid boundary.

• Input: the grid above
• Output: 1
• Explanation: all nine 1-cells form one connected landmass

Counter-example showing two islands:

• Input: the grid above
• Output: 3
• Explanation: the top-left cluster, the lone center cell, and the bottom-right pair are each isolated from one another

Intuition

The problem is really asking: how many connected components made of '1' cells exist in the grid? Every time you stumble on a '1' you haven't visited yet, you've found the first cell of a brand-new island. The trick is to immediately flood-fill that entire island — marking every connected land cell as visited — so you never count the same island twice.

Solution — DFS Flood Fill

Each unvisited '1' cell triggers an island count increment and a depth-first flood fill that sinks every reachable land cell by flipping it to '0'. When the DFS unwinds, all cells belonging to that island are neutralised, and the outer loop continues scanning for the next unseen island.

1. If the grid is empty, return 0.
2. Iterate every cell (r, c) in the grid.
3. When grid[r][c] == '1', increment the island counter and call sink_island(r, c).
4. In sink_island: if the cell is out of bounds or is '0', return immediately.
5. Mark the cell '0' (visited), then recurse into all four neighbours.
6. After the full scan, return the island counter.

1def numIslands(grid: list[list[str]]) -> int:
2    if not grid:
3        return 0
4
5    rows, cols = len(grid), len(grid[0])
6    island_count = 0
7
8    def sink_island(r: int, c: int) -> None:
9        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':
10            return
11        grid[r][c] = '0'  # mark visited before recursing to avoid revisiting
12        sink_island(r + 1, c)
13        sink_island(r - 1, c)
14        sink_island(r, c + 1)
15        sink_island(r, c - 1)
16
17    for r in range(rows):
18        for c in range(cols):
19            if grid[r][c] == '1':
20                island_count += 1
21                sink_island(r, c)
22
23    return island_count

Time: O(m × n) — every cell is visited at most twice: once by the outer loop and once by a flood fill.

Space: O(m × n) — the DFS call stack depth is bounded by the number of cells in the largest island; in the worst case (the entire grid is one snake-shaped island) this is m × n frames.

Complexity Summary

Common Mistakes

• Marking the cell visited after recursing instead of before — if you flip '0' only after the four recursive calls return, each neighbour will see the current cell as unvisited and recurse back into it, causing infinite recursion.
• Checking grid[r][c] before the bounds check — grid[r][c] throws an index-out-of-bounds error when r or c is out of range; always validate indices first in the same condition expression.
• Counting individual '1' cells instead of connected components — the outer loop should only increment island_count when it encounters a '1', not on every cell; the flood fill is what ensures you count groups, not cells.
• Forgetting one of the four directions — islands can be connected up, down, left, and right; dropping any direction will incorrectly split large islands into multiple smaller ones.
• Using a separate visited set but adding cells after the recursive calls — the same re-entry bug as the first point; you must add (r, c) to visited before recursing into its neighbours.

Related Problems

• Max Area of Island — same flood fill structure, but accumulate the size of each component instead of just counting it
• Rotting Oranges — BFS variant on a grid where the order of spreading matters
• Flood Fill — the primitive flood-fill operation in isolation, without the connected-component counting layer
• Number of Provinces — counting connected components in an adjacency matrix rather than a 2D grid
• Surrounded Regions — flood fill starting from the boundary to decide which interior regions to flip