Pattern visualizer

Number of Islands II

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. 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]..

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

time O(K α(m*n))space O(m*n)step 1 / 10

3x3 grid, all water

0,0

0,1

0,2

1,0

1,1

1,2

2,0

2,1

2,2

line 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.

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

Where to practice Graph

Practice Graph problems All Graph problems Back to roadmap