LeetCode 200 · Flood Fill · DFS

Number of Islands

MediumCount connected components of land in a 2-D grid.
Given an m × n grid of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and formed by connecting adjacent land cells horizontally or vertically.

Walkthrough

boards:
click any cell to toggle land / water
1
function numIslands(grid) {
2
  let count = 0;
◄
3
  const sink = (r, c) => {
4
    if (oob(r, c) || grid[r][c] !== '1') return;
5
    grid[r][c] = '0';
6
    sink(r+1,c); sink(r-1,c); sink(r,c+1); sink(r,c-1);
7
  };
8
  for (let r = 0; r < rows; r++)
9
    for (let c = 0; c < cols; c++)
10
      if (grid[r][c] === '1') { count++; sink(r, c); }
11
  return count;
12
}
count = 0
water (0)land (1)sunk → 0, colored by islandscanning
STEP 0 / 31 · line 2
Start
Scan the grid row by row. Each unvisited land cell starts a new island, which we flood-fill.

Intuition

Each island is a connected component of land cells. Counting islands = counting components.

Scan the grid; the first time you hit an unvisited land cell, you have found a new island.

Flood-fill (DFS) from that cell, sinking every connected land cell to water so it is not counted again.

The algorithm

  1. 01Walk every cell (r, c) of the grid.
  2. 02When you find a '1', increment the island count.
  3. 03Run a DFS that sinks the cell and recurses into its four neighbours.
  4. 04The sink marks land as water, so each island is counted exactly once.

Reference implementation

1
function numIslands(grid) {
2
  if (!grid.length) return 0;
3
  const rows = grid.length, cols = grid[0].length;
4
  let count = 0;
5
6
  const sink = (r, c) => {
7
    if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] !== '1') return;
8
    grid[r][c] = '0'; // mark visited
9
    sink(r + 1, c);
10
    sink(r - 1, c);
11
    sink(r, c + 1);
12
    sink(r, c - 1);
13
  };
14
15
  for (let r = 0; r < rows; r++) {
16
    for (let c = 0; c < cols; c++) {
17
      if (grid[r][c] === '1') {
18
        count++;
19
        sink(r, c);
20
      }
21
    }
22
  }
23
  return count;
24
}

Complexity

Time
O(m · n) — every cell is visited a constant number of times.
Space
O(m · n) worst case for the recursion stack.