Union-Find — Number of Islands II

↗ LeetCode: Number of Islands II · Hard · pattern chapter →

Asked atGoogleAmazonMeta

You have an m × n grid of water. Given positions where each (r, c) becomes land, return count of islands after each addition.

Example 1 — m=3, n=3, positions=[[0,0],[0,1],[1,2],[2,1]] → [1,1,2,3]Example 2 — m=1, n=1, positions=[[0,0]] → [1]Example 3 — m=3, n=3, positions=[[0,0],[0,0]] → [1,1] (duplicate placement is a no-op)

Constraints — 1 ≤ m·n ≤ 10⁴. Naive re-scan after every insert is O(k · mn) — k inserts × mn cells = 10⁸ ops = TLE. Union-Find is O(k · α(mn)) = 10⁴ · 4 = 4·10⁴.

Progressive Hints

Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.

---

⏱️Interview timer00:00

Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.

Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.

Approach 1 — DFS after each addition

O(k · m·n). Too slow for streaming.

Approach 2 — Streaming Union-Find (canonical)

Insight. Each new land cell either starts a new island or merges into existing neighbors. Union-Find handles both:

Mark cell as land; count++.
For each of 4 neighbors that is land AND has a different root: union; count--.

java

List<Integer> numIslands2(int m, int n, int[][] positions) {
    int[] parent = new int[m * n];
    Arrays.fill(parent, -1);
    int[][] D = {{1,0},{-1,0},{0,1},{0,-1}};
    List<Integer> out = new ArrayList<>();
    int count = 0;
    for (int[] p : positions) {
        int r = p[0], c = p[1], id = r * n + c;
        if (parent[id] != -1) { out.add(count); continue; }
        parent[id] = id; count++;
        for (int[] d : D) {
            int nr = r + d[0], nc = c + d[1], nid = nr * n + nc;
            if (nr < 0 || nc < 0 || nr >= m || nc >= n || parent[nid] == -1) continue;
            if (union(parent, id, nid)) count--;
        }
        out.add(count);
    }
    return out;
}
int find(int[] p, int x) { return p[x] == x ? x : (p[x] = find(p, p[x])); }
boolean union(int[] p, int a, int b) {
    int ra = find(p, a), rb = find(p, b);
    if (ra == rb) return false;
    p[ra] = rb; return true;
}

Execution Trace

UF stream — positions=[[0,0],[0,1],[1,2],[2,1]]

Complexity — Time O(k · α(m·n)); Space O(m·n).

Try it yourself

Complexity summary

Approach	Time	Space	Grade
DFS per add	O(k · m·n)	O(m·n)	too slow streaming
Union-Find streaming	O(k · α(m·n))	O(m·n)	canonical

When to use which

Streaming connectivity → Union-Find.
Static → DFS/BFS flood fill.
Deletion of land → offline reverse: process removals as additions.

✨AI Study CompanionBeta

Was this page helpful?

📚 Related problems

Union-Find — Number of Islands II ​

Approach 1 — DFS after each addition ​

Approach 2 — Streaming Union-Find (canonical) ​

Try it yourself ​

Complexity summary ​

When to use which ​

Related problems ​