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

In plain English, we are given a 2D matrix representing a map. 1s are land and 0s are water. An island is formed by connecting adjacent lands horizontally or vertically (diagonals do not count). We need to return the total number of distinct islands. The grid dimensions can range up to 300x300. Edge cases to consider include an empty grid, a grid entirely made of water (returns 0), or a grid entirely made of land (returns 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 ELI5 Analogy

Think of the grid as a physical map on a table, and you are holding a bucket of red paint. You read the map like a book—left to right, top to bottom. Every time you find an unpainted piece of land ('1'), you know you've discovered a new island. You immediately pour the red paint on it. The paint spreads to all connected land horizontally and vertically. By the time the paint stops spreading, the entire island is colored red (or in our code, changed to '0'). As you continue reading the map, you will never double-count this island because it no longer looks like unvisited land.

What about a Brute Force Approach?

A naive brute force idea might be to find all '1's and try to group them into sets by repeatedly checking if any '1' is next to a known set, merging sets when they touch. Why is this too slow? If you have N total land cells, repeatedly scanning to merge adjacencies could take O(N^2) time in the worst case (imagine a long snake-like island where you discover the connections one by one). It wastes an immense amount of time re-evaluating the same boundaries. The flood-fill optimally eliminates this waste by exhaustively consuming an entire island the moment it is found, ensuring every cell is processed exactly once.

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.

Code Walkthrough & Trace

Let's trace a small 2x2 grid:

1 0
1 1

Step	Action	State / Recursion
1	Outer loops start at (r=0, c=0)	grid[0][0] is '1'. count becomes 1. Call sink(0, 0).
2	sink(0, 0) executes	Marks grid[0][0] = '0'. Grid is now [[0, 0], [1, 1]]. Recurse to neighbors.
3	sink calls on neighbors	sink(1, 0) is called. (Others go out of bounds or hit '0').
4	sink(1, 0) executes	Marks grid[1][0] = '0'. Grid is now [[0, 0], [0, 1]]. Recurse to neighbors.
5	sink(1, 1) executes	Marks grid[1][1] = '0'. Grid is now [[0, 0], [0, 0]]. All connected components are sunk.
6	Outer loops continue	r=0, c=1 is '0'. r=1, c=0 is '0'. r=1, c=1 is '0'. No more '1's found.
7	End	Returns count = 1.

Key lines explained:

1. if grid[r][c] != '1': return - This handles out-of-bounds (if checked before) AND our visited logic all in one place. If it's water, or land we already sank, stop exploring this path.
2. grid[r][c] = '0' - Crucial line. If you removed this, sink(0, 0) would call sink(1, 0), which would call sink(0, 0), creating an infinite loop.

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. To break it down like you're talking to a friend: "We iterate through the entire grid once with our nested loops. That takes O(rows \times cols). When we find an island, our DFS visits its cells. But because we mutate the cell to '0' immediately, we will never process that cell again inside another DFS, and our outer loop will just skip over it. Therefore, each cell is processed at most a small, constant number of times."

Space is O(rows \times cols) in the worst case, for the recursion stack or the queue, when the grid is one giant island. In that scenario, a DFS trace snakes through every single cell before hitting a dead end, accumulating rows \times cols frames on the call stack. For BFS, the queue holds at most the perimeter of the expanding search, which is bounded by O(\min(rows, cols)), but the theoretical worst-case space bound usually simplifies to the same total dimensions depending on grid shapes.

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.