Number of islands II

Hard

Union-find as the land appears

Problem

Given a grid and a sequence of land additions, return the number of islands after each addition.

In simple words

Add land one at a time with union-find: each new cell is a new island, merging with any land neighbours.

The idea

Each added land cell starts as its own island, so increment the count and then union with any adjacent land, decrementing once per successful union. Union-find handles the incremental merging that a re-run of DFS would redo from scratch each time.

The trick

Adding land: count++, then count-- for each successful union.
Guard against the same cell being added twice.
O(k α(n)) for k additions rather than O(k × rows × cols).

←→stepspaceplay

1/10

Optimal

timeO(α(n))spaceO(n)

Almost constant per op.

1function find(x) {2  while (p[x] !== x) { p[x] = p[p[x]]; x = p[x]; }3  return x;4}5function union(a, b) {6  a = find(a); b = find(b);7  if (a === b) return false;8  if (rank[a] < rank[b]) [a, b] = [b, a];9  p[b] = a; if (rank[a] === rank[b]) rank[a]++;10  return true;11}

Input

nodes: 5, 0 edges

Memory

groups: —

Output

groups: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: m=3, n=3, positions=[[0,0],[0,1],[1,2],[2,1]]
Output:: [1, 1, 2, 3]
Explanation:: Island count after each land addition.

Example 2

Input:: m=1, n=1, positions=[[0,0]]
Output:: [1]
Explanation:: One cell → 1 island.

Example 3

Input:: m=2, n=2, positions=[[0,0],[0,1]]
Output:: [1, 1]
Explanation:: Adjacent lands merge → 1.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.