200. Number of Islands

Given a grid of '1' (land) and '0' (water), return the number of islands: groups of land connected horizontally or vertically.

Start with one set per land cell. Union each land cell with its land neighbors to the right and below. Every successful union merges two islands, so subtract one.

1function numIslands(grid: string[][]): number {
2  const m = grid.length, n = grid[0].length, parent: number[] = [];
3  let count = 0;
4  const find = (x: number): number => (parent[x] === x ? x : (parent[x] = find(parent[x])));
5  for (let r = 0; r < m; r++) for (let c = 0; c < n; c++)
6    if (grid[r][c] === "1") { parent[r * n + c] = r * n + c; count++; }
7  for (let r = 0; r < m; r++) for (let c = 0; c < n; c++) {
8    if (grid[r][c] !== "1") continue;
9    for (const [x, y] of [[r + 1, c], [r, c + 1]]) {
10      if (x >= m || y >= n || grid[x][y] !== "1") continue;
11      const a = find(r * n + c), b = find(x * n + y);
12      if (a !== b) { parent[a] = b; count--; }
13    }
14  }
15  return count;
16}

islands = 7

root of each land cell

0	1
5	6
		12
			18	19

Each of the 7 land cells is its own set.

1 / 0

Space: play/pause · ←/→: step