DSA Tracker

Visualize

Number of Islands II

Union-Find on a growing grid: one merge per land-adjacent neighbour

time O(K α(m*n))space O(m*n)

Recomputing connected components from scratch after every addition costs O(m*n) per query. Instead give every cell a disjoint-set slot: placing land always adds one new island first, then a union with any already-land neighbour merges two islands into one and removes exactly one from the count. The picture below draws the full grid adjacency as a faint scaffold — the accent edges are the ones that currently connect two land cells, and the badge on each land cell is its current DSU root.

Details

Animated on: 3x3 grid, all water — land is added one cell at a time at (0,0), (0,1), (1,2), (2,1). Return the island count after EACH addition: [1, 1, 2, 3].

Problem:Number of Islands IIHard

Union-Find on a growing grid: one merge per land-adjacent neighbour

step 1 / 10

3x3 grid, all water

3 x 3 grid, every cell starts as water. Land arrives one cell at a time at (0,0), (0,1), (1,2), (2,1) — after EACH arrival we need the island count, and re-scanning the whole grid every time would be O(K * m * n). Track connectivity incrementally with a disjoint-set instead: one flattened index per cell, union on placement.

Pseudocode
1FUNCTION numIslands2(m, n, positions):
2  parent <- ARRAY OF SIZE m * n, EACH -1
3  count <- 0, out <- []
4  FOR EACH (r, c) IN positions
5    idx <- r * n + c
6    parent[idx] <- idx
7    count <- count + 1
8    FOR EACH (nr, nc) IN NEIGHBORS(r, c)
9      nidx <- nr * n + nc
10      IF VALID(nr, nc) AND parent[nidx] != -1 AND FIND(nidx) != FIND(idx)
11        UNION(idx, nidx)
12        count <- count - 1
13    APPEND count TO out
14  RETURN out

← / → step · space play · Home restart

Every step in words

Show all 10 steps
  1. 3 x 3 grid, every cell starts as water. Land arrives one cell at a time at (0,0), (0,1), (1,2), (2,1) — after EACH arrival we need the island count, and re-scanning the whole grid every time would be O(K * m * n). Track connectivity incrementally with a disjoint-set instead: one flattened index per cell, union on placement.
  2. Place land at (0,0): it starts as its own island, so the running count goes to 1 before we've even looked at its neighbours.
  3. All 4 neighbours of (0,0) are water, so nothing to merge — count stays 1.
  4. Place land at (0,1): it starts as its own island, so the running count goes to 2 before we've even looked at its neighbours.
  5. Its neighbours 0,0 are already land — merging it into this island drops the count by 1, to 1.
  6. Place land at (1,2): it starts as its own island, so the running count goes to 2 before we've even looked at its neighbours.
  7. All 4 neighbours of (1,2) are water, so nothing to merge — count stays 2.
  8. Place land at (2,1): it starts as its own island, so the running count goes to 3 before we've even looked at its neighbours.
  9. All 4 neighbours of (2,1) are water, so nothing to merge — count stays 3.
  10. After all 4 additions the answer array is [1, 1, 2, 3] — one entry per position, read straight off the running count after each placement. RETURN out.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Number of Islands II in the editorAll Graph problemsBack to roadmap