Union-Find — Number of Provinces

↗ LeetCode: Number of Provinces · Medium · pattern chapter →

Asked atAmazonGoogleMetaLinkedIn

Given isConnected[n][n] (adjacency matrix; 1 if direct road), return the number of connected components.

Example 1 — [[1,1,0],[1,1,0],[0,0,1]] → 2Example 2 — [[1,0,0],[0,1,0],[0,0,1]] → 3

Constraints — 1 ≤ n ≤ 200. Brute DFS/BFS from every city is O(n²) = 4·10⁴ ops at n=200 — repeated 10⁶ times per hour for a static-snapshot workload burns real CPU. Union-Find with path compression + union by rank is O(n²·α(n)) ≈ 4·10⁴ ops — same asymptote, but the DSU wins the moment edges start arriving dynamically.

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 from each unvisited city

Intuition. For each unvisited node, DFS the whole component; each fresh start = new province.

int findCircleNumDFS(int[][] g) {
    int n = g.length, count = 0;
    boolean[] seen = new boolean[n];
    for (int i = 0; i < n; i++) if (!seen[i]) { dfs(i, g, seen); count++; }
    return count;
}
void dfs(int u, int[][] g, boolean[] seen) {
    seen[u] = true;
    for (int v = 0; v < g.length; v++) if (g[u][v] == 1 && !seen[v]) dfs(v, g, seen);
}

Complexity — Time O(n²); Space O(n) recursion.

---

Approach 2 — BFS from each unvisited city

Intuition. Same as DFS but iterative (avoids stack overflow on dense graphs).

Complexity — Time O(n²); Space O(n) queue. Same asymptotic; different stack risk.

---

Approach 3 — Union-Find (Disjoint Set Union) with union-by-size + path compression

Insight from DFS/BFS. DFS/BFS re-traverses each component. Union-Find pre-computes the parent forest as we scan edges once; the final component count = distinct roots.

Trap. Without union-by-size (or rank), naive union chains linearly → O(n) per find. With union-by-size + path compression, each op is O(α(n)) ≈ O(1).

int findCircleNum(int[][] g) {
    int n = g.length;
    int[] parent = new int[n], size = new int[n];
    for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
    int count = n;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (g[i][j] == 1 && union(parent, size, i, j)) count--;
    return count;
}
int find(int[] parent, int x) {
    while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
    return x;
}
boolean union(int[] parent, int[] size, int a, int b) {
    int ra = find(parent, a), rb = find(parent, b);
    if (ra == rb) return false;
    if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
    parent[rb] = ra; size[ra] += size[rb];
    return true;
}

Execution Trace

Union-Find — [[1,1,0],[1,1,0],[0,0,1]]

Step 1 / 3each city its own root

Complexity — Time O(n² α(n)) ≈ O(n²); Space O(n). Same big-O as DFS but incremental — supports streaming edges.

---

Try it yourself

Complexity summary

Approach	Time	Space
DFS from each city	O(n²)	O(n)
BFS from each city	O(n²)	O(n)
Union-Find	O(n² α(n))	O(n)

When to use which

• Static graph, one query → DFS/BFS are fine.
• Dynamic edges (streaming) → Union-Find (only structure that supports incremental unions).
• Also need "are these two nodes connected?" → Union-Find with path compression gives O(1) queries.

✨AI Study CompanionBeta

Related problems (same ladder applies)

• Accounts Merge — union emails belonging to the same person
• Redundant Connection — find the edge whose two endpoints are already connected
• Number of Islands II — streaming version of Number of Islands
• Min Cost to Connect All Points — Kruskal's MST via Union-Find

Was this page helpful?