4.20.1 — Number of Islands

LeetCode 200 · Medium · ★ Blind 75

The problem

Count the islands in a grid of '1' (land) and '0' (water). Cells connect horizontally and vertically, not diagonally.

1 1 0 0 0
1 1 0 0 0
0 0 1 0 0        →  3
0 0 0 1 1

The pattern

Scan every cell. When you meet a piece of land that has not been seen yet, that is a new island — so add one to the count, then flood the entire island so its other cells are never counted again.

The flood is a DFS or BFS from that cell, marking everything it reaches.

The guard "only start from an unvisited cell" is the whole algorithm. It is the same idea as the run-start check in 4.4.9 Longest Consecutive Sequence: do the work only from one agreed member of each group.

The solution

Python

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0
        rows, cols = len(grid), len(grid[0])

        def sink(r: int, c: int):
            if r < 0 or r >= rows or c < 0 or c >= cols:
                return
            if grid[r][c] != '1':
                return                       # water, or already sunk
            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':        # a new island
                    count += 1
                    sink(r, c)

        return count

TypeScript

function numIslands(grid: string[][]): number {
  if (!grid.length) return 0;
  const rows = grid.length, cols = grid[0].length;

  function sink(r: number, c: number): void {
    if (r < 0 || r >= rows || c < 0 || c >= cols) return;
    if (grid[r][c] !== '1') return;
    grid[r][c] = '0';
    sink(r + 1, c); sink(r - 1, c); sink(r, c + 1); sink(r, c - 1);
  }

  let count = 0;
  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      if (grid[r][c] === '1') { count++; sink(r, c); }

  return count;
}

Mark before recursing. Setting grid[r][c] = '0' before the four calls is what stops the search coming straight back to this cell and looping forever.

Never restore it. A cell belongs to exactly one island; putting the '1' back would recount it. This is the point where backtracking habits go wrong — compare 4.18.6 Word Search, where the restore is mandatory because you are finding paths, not regions.

The grid is the visited set. No extra structure needed. If you must not modify the input, keep a separate visited array of the same shape — same algorithm, O(rows × cols) extra space.

The BFS version, and when you need it

DFS recursion depth can reach rows × cols. On a 1000×1000 grid that is a million stack frames, which overflows in Python (default limit around 1000) and in most languages.

BFS has no recursion at all:

from collections import deque

def bfs(r, c):
    queue = deque([(r, c)])
    grid[r][c] = '0'                                  # mark on ENQUEUE
    while queue:
        cr, cc = queue.popleft()
        for nr, nc in ((cr+1,cc), (cr-1,cc), (cr,cc+1), (cr,cc-1)):
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                grid[nr][nc] = '0'                    # mark BEFORE enqueueing
                queue.append((nr, nc))

Marking on enqueue, not on dequeue, is essential. If you mark when you take a cell out, the same cell can be added several times before it is ever processed, and the queue grows far beyond the grid size.

Both are O(rows × cols). Use DFS for brevity, BFS when the grid is large.

Complexity

O(rows \times cols) time — every cell is examined a constant number of times, because once sunk it is never entered again.

Space is O(rows \times cols) in the worst case, for the recursion stack or the queue, when the grid is one giant island.

Where this goes next

Eight problems in this chapter are this flood fill with one thing changed:

problem	change
Max Area of Island	the flood returns a count instead of nothing — 4.20.3
Surrounded Regions	flood from the border to mark survivors — 4.20.5
Pacific Atlantic	flood from two edge sets and intersect — 4.20.4
Number of Distinct Islands	record each island's shape as a fingerprint
Number of Closed Islands	flood the border first, then count what remains
Number of Provinces	the same on an adjacency matrix instead of a grid
Flood Fill (LeetCode 733)	the same, changing colours

Union-find also solves this: union each land cell with its land neighbours, and count the components. It is O(rows \times cols \times \alpha) and more code. It earns its place only when land cells are added over time and you must report the count after each addition — that is "Number of Islands II", and it is the version where DFS would have to re-scan everything after every addition.

What the interviewer will push on

"Why does counting from an unvisited cell work?" Every island is entered exactly once, from whichever of its cells the scan meets first.

"Do you restore the grid?" No. Regions are not paths.

"What if you cannot modify the input?" A separate visited array.

"What about stack overflow?" BFS, or an explicit stack. Give the million-frame figure.

"What if land is added one cell at a time?" Union-find, because a fresh flood fill after every addition is O(n) each time.

One thing to volunteer: say that the grid is the visited set and that you are deliberately not restoring it. Naming the difference from backtracking shows you know both patterns rather than one habit.

Next: 4.20.2 Clone Graph — a traversal that builds something as it goes.