Union-Find (Disjoint Set Union)

▶

8–12 min

Pattern Video

Union-Find — Interactive Walkthrough

🎬 Video walkthrough coming soon. Subscribe to be notified when it drops.

Pattern Progress

Not started

0%

Problems solved0 / 9

Quiz scoreNot taken

Why union-find exists — the story

You're a backend engineer at Facebook. A new signup arrives: "Alice, alice@work.com." Your dedup pipeline needs to answer: is this the same person as an existing user? Signals include shared emails, shared phone numbers, shared devices, shared friend graphs. Every new signal is an edge.

The honest first attempt: for each new signup, run BFS from that node across all known signal edges, collecting the connected component. If it overlaps with an existing user's component, they're the same person. Correct. Simple.

But Facebook adds 300 signups per second and has ~10⁹ users. Each BFS is O(V + E). Even amortized, that's ~10¹² operations per second globally — 200,000× more than a single machine can do. The naive approach is a fleet-wide meltdown.

Worse: for the "same-person?" query, you don't need to rebuild the component. You just need to know which representative user Alice already collapses to. That question — "do these two nodes belong to the same group?" — has its own data structure: Union-Find. It answers find(a) in near-O(1) using path compression, and union(a, b) in the same. Total cost across m operations is O(m · α(n)) where α is the inverse Ackermann function — effectively constant for any real input. For Facebook: 300 lookups per second, each ~10ns instead of 10⁴ns. A 1,000× per-query speedup and no fleet meltdown.

This isn't just an interview trick. Every incremental clustering system on Earth uses Union-Find: Kruskal's MST (1956), image segmentation (connected components labeling), Percolation theory (Sedgewick's canonical example), Git's tag-graph reachability, Kubernetes' pod-affinity solver. Every LeetCode "Number of Provinces / Connected Components / Accounts Merge" problem is testing this.

Imagine edges arriving one at a time: city 0 connects to city 1, account A shares an email with account B, stone x shares a row with stone y. The brute-force instinct is to rebuild the connected components with DFS/BFS after every new edge. That works for one static graph, but it repeats old work when all you need is "are these two already in the same group?"

Can we do better? Union-Find keeps one representative root per group. Each new edge either merges two roots or tells you the edge was redundant. Path compression and union by rank make those repeated membership checks nearly constant time.

Dynamic connectivity as edges arrive. Maintain a parent pointer per node. find(x) walks to the root (with path compression flattening the trail); union(a,b) attaches the shorter tree under the taller (union by rank). Both amortize to near-O(1) — inverse Ackermann.

Key Insight

Union-Find is not a tree traversal algorithm; it's a set-membership structure. When you need "are these two things in the same group?" or "how many groups?" as edges arrive, reach for it before BFS/DFS.

How to read it: Before compression, find(a) has to climb every parent pointer until it reaches the representative root. On the return trip, path compression rewrites each visited node's parent to the root. The set membership is unchanged, but future find calls on a, b, c, or d are nearly instant.

Key Insight — path compression and union-by-rank are both essential.

Path compression alone gives O(log n) amortized. Union-by-rank alone also gives O(log n) amortized. Together they give O(α(n)) — effectively constant. Skipping either one bumps you back to log; skipping both makes worst-case O(n). Interviewers ask about both separately to test whether you memorized one and skipped the other.

Invariant — rank is a height upper bound, not the exact height. Union-by-rank tracks rank[root], which is an upper bound on the tree's height (rank only increments on equal-rank unions). Path compression may reduce the actual height without updating rank; that's fine — rank is used only for the union comparison, not for correctness of find.

Trap — using `size[]` and `rank[]` interchangeably.

Both work as tie-breaks for union, but with subtly different semantics. rank-by-height gives O(α(n)) with the classical Tarjan analysis. size-by-cardinality also gives O(α(n)) but requires a different proof. Pick one convention per implementation. Mixing them (attaching by rank in union, comparing by size in a helper) breaks the amortized analysis.

Trap — updating parent without also updating rank.

After union-by-rank, only one of the two rank values changes (the winner's, on tie). Some candidates copy over rank on every union, which corrupts the height bound and degrades to O(log n). Rule: rank[winnerRoot] += (rank[winnerRoot] == rank[loserRoot] ? 1 : 0).

When to use it — dynamic connectivity

Recognize by

• dynamic connectivity — edges arrive over time; answer "same group?" as they do
• "count connected components / groups / islands"
• "redundant connection" (find the edge that creates a cycle)

Step 1 / 10

When NOT to use it

You need to walk the components (traversal, distances, colouring) — Union-Find only tells you set membership, not adjacency. Also, if you must remove edges (not just add), Union-Find doesn't support that natively — either process events offline in reverse or use link-cut trees.

History — Galler-Fischer 1964, Tarjan 1975

The disjoint-set data structure was introduced by Bernard Galler and Michael Fischer in 1964 in their paper "An improved equivalence algorithm" (Communications of the ACM 7(5):301-303). Their algorithm used simple parent-pointers with no rank or path compression — worst-case O(n) per operation, still faster than the previous best.

The breakthrough came in 1975 with Robert Tarjan's O(m · α(n)) analysis. Tarjan (later a Turing Award winner in 1986) proved that union-by-rank combined with path compression gives an amortized per-operation cost of α(n) — the inverse Ackermann function. For all practical inputs (n < 2^{2^{2^{16}}}), α(n) ≤ 4. So Union-Find is effectively constant-time, a wildly counterintuitive result given the tree structure suggests O(log n).

Tarjan also proved this bound is tight — no comparison-based DSU can do better in general. That means the algorithm we teach in this chapter is provably optimal (up to constants), a rare and beautiful result in algorithm design.

Real-world adoption:

• Kruskal's Minimum Spanning Tree (1956) — the classic application; every network-optimization system uses it.
• Image segmentation (connected-component labeling) — every 2D image processing pipeline runs union-find over pixels.
• Percolation theory — used to model how fluids flow through porous materials; Sedgewick's textbook uses it as the flagship example.
• Kubernetes' scheduler — pod affinity and anti-affinity rules are evaluated via union-find over node groups.
• Compiler optimization: Steensgaard's alias analysis (1996) treats pointer-may-alias as a union-find on variable types. Every optimizing compiler (GCC, LLVM, Rust's borrow checker) runs this.
• Git — determining whether two commits share a common ancestor uses union-find over the commit graph.

When you tell an interviewer "Union-Find with path compression and union-by-rank, O(α(n)) amortized," you're citing one of the top-10 most-used data structures in all of computer science.

Canonical problem walkthrough — Number of Provinces

Problem (↗ LeetCode): There are n cities. Some are directly connected. An n × n matrix isConnected[i][j] = 1 means city i and city j are directly connected. A province is a group of cities transitively connected (direct or indirect). Return the number of provinces.

Approach 1 — Brute force: BFS from every city

For each city that hasn't been visited yet, run a BFS to mark all cities in the same province. Each such BFS starts a new province.

int findCircleNumBFS(int[][] isConnected) {
    int n = isConnected.length;
    boolean[] visited = new boolean[n];
    int provinces = 0;
    for (int i = 0; i < n; i++) {
        if (visited[i]) continue;
        provinces++;
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(i);
        visited[i] = true;
        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int v = 0; v < n; v++) {
                if (isConnected[u][v] == 1 && !visited[v]) {
                    visited[v] = true;
                    queue.offer(v);
                }
            }
        }
    }
    return provinces;
}

Complexity: O(n²) time (each cell visited once), O(n) space (visited + queue). For n = 200 (LeetCode's cap), that's 40,000 ops — instant. Correct and idiomatic for this size.

Why show it first? BFS/DFS is the honest reference for connected-components on a static input. If the graph is fixed and the problem asks "count components once," BFS beats Union-Find in constant factors. State this out loud in an interview — it signals you know when not to over-engineer.

Approach 2 — Union-Find (the pattern-teaching answer)

Every isConnected[i][j] == 1 is an edge that should be unioned. Count the number of distinct roots at the end.

int findCircleNum(int[][] isConnected) {
    int n = isConnected.length;
    int[] parent = new int[n];
    int[] rank = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i;
    int provinces = n;

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {         // upper triangle: matrix is symmetric
            if (isConnected[i][j] == 1) {
                if (union(parent, rank, i, j)) provinces--;
            }
        }
    }
    return provinces;
}

int find(int[] parent, int x) {
    if (parent[x] != x) parent[x] = find(parent, parent[x]);  // path compression
    return parent[x];
}

boolean union(int[] parent, int[] rank, int a, int b) {
    int ra = find(parent, a), rb = find(parent, b);
    if (ra == rb) return false;                    // already in same set
    if (rank[ra] < rank[rb])       parent[ra] = rb;
    else if (rank[ra] > rank[rb])  parent[rb] = ra;
    else { parent[rb] = ra; rank[ra]++; }
    return true;
}

Complexity: O(n² · α(n)) time, O(n) space. For n = 200, that's still ~40,000 ops but with a smaller α(n) constant (effectively O(1) per union). Slightly slower than pure BFS in absolute wall time, but far more general — you can now handle dynamic edges arriving one at a time in O(α(n)) each, which BFS cannot.

Interview commentary to voice out loud:

• "Brute force is O(n²) with BFS. Union-Find gives us the same asymptotic complexity for static input."
• "But if the problem gets extended — 'edges arrive one at a time,' 'friends being introduced,' 'incremental cluster merging' — BFS re-runs from scratch on each edge, while Union-Find handles it in O(α(n)) per edge."
• "Path compression flattens the tree during find; union-by-rank prevents linear chains. Both are essential to hit α(n)."
• "The union returns boolean so we decrement the province counter only when a merge actually happens (not when both were already in the same set)."

Approach 3 — DFS-based reference (equivalent to BFS)

For completeness, DFS is one-liner-different from BFS:

int findCircleNumDFS(int[][] isConnected) {
    int n = isConnected.length;
    boolean[] visited = new boolean[n];
    int provinces = 0;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            provinces++;
            dfs(isConnected, visited, i);
        }
    }
    return provinces;
}

void dfs(int[][] c, boolean[] visited, int u) {
    visited[u] = true;
    for (int v = 0; v < c.length; v++)
        if (c[u][v] == 1 && !visited[v]) dfs(c, visited, v);
}

When to use which: BFS avoids recursion depth issues on very deep chains. DFS is 1 line shorter. Union-Find is the answer when the problem may extend to dynamic edges.

Complexity ladder

Approach	Time	Space	Best use
BFS / DFS from each unvisited	O(n²)	O(n)	Static input, single-shot count
Union-Find	O(n² · α(n))	O(n)	Interview default; extends cleanly to dynamic
Adjacency list + Kruskal-style edge stream	O(E · α(n))	O(n)	Sparse graphs where edges are given as a list, not a matrix

---

Union-Find (Disjoint Set Union) Medium

↗ LeetCode: Number of Provinces

Mark as solved

Interactive · Data-Structure Operation

Union-Find operations (find with path compression, union by rank)

Step 1 / 5parent[]: idx→parent. Chain 0→1→2→3 (root 3).

1

0

2

1

3

2

3

3

How to read it: Union first finds each set's root, then attaches one root under the other; later finds can compress paths so all members jump straight to the representative.

Problem

Given an n×n friendship matrix, count the number of provinces — connected groups of directly or indirectly connected people.

Constraints: 1 ≤ n ≤ 200; matrix symmetric with 1 on the diagonal.

Example 1: [[1,1,0],[1,1,0],[0,0,1]] → 2.

Example 2: [[1,0,0],[0,1,0],[0,0,1]] → 3 because every city is isolated.

Solution — brute force

Brute force for provinces is to run DFS/BFS over the friendship matrix, marking every connected city once. That solves this static problem in O(n²) time and O(n) space, which is fine for a single matrix but does not support many online connectivity checks elegantly. Union-Find turns each friendship into a merge and answers group membership through roots, with path compression and rank keeping operations effectively constant.

visited = set()
provinces = 0
for each city i:
    if i is unvisited:
        provinces++
        DFS/BFS through every j where isConnected[i][j] == 1
return provinces

Brute force complexity: O(n²) time to scan the matrix and O(n) space for visited/search state.

Solution — optimized

Forest of parent pointers with path compression + union by rank/size → α(n) amortized per operation.

Invariant

Every element in a set points (eventually) to one canonical root; find returns and compresses toward it.

Union-Find — path compression flattens trees; union-by-rank keeps them shallow, giving ~O(1) ops.

How to read it: Each group is a little tree, and the node at the top (the root) is the group's name. `find(x)` walks up parent links to that root, and along the way it re-points nodes straight at the root — "path compression" — so next time is instant. `union(a,b)` finds both roots; if they're the same, a and b are already together, otherwise it hangs the shorter tree under the taller one so things stay flat. These two tricks make every operation effectively constant time.

Java

class DSU {
    int[] parent, rank;
    DSU(int n) {
        parent = new int[n]; rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int find(int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } // path compression
        return x;
    }
    boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;                    // already connected (a cycle in undirected)
        if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }
        parent[rb] = ra;
        if (rank[ra] == rank[rb]) rank[ra]++;
        return true;
    }
}

Trace it

isConnected=[[1,1,0],[1,1,0],[0,0,1]]. Union cities 0 and 1 (they share an edge); city 2 stays alone → 2 provinces (2 disjoint sets).

Execution Trace

Number of Provinces — 3 cities, edge 0-1

Step 1 / 3start: each city its own root

Time Complexity

Time O(n² · α(n)) for scanning the matrix and unioning friendships; each DSU operation is effectively constant.

Space Complexity

Space O(n) for the parent and rank arrays.

Learning notes

• Why initialize parent[i] = i? — every city starts as its own representative.
• Why path compression in find? — it flattens future root lookups.
• Why union by rank? — attaching shorter trees under taller ones keeps finds shallow.
• Why return false when roots match? — the two nodes were already in the same component.
• Why count roots/components after unions? — provinces are connected components, not direct friendships.
• Why DSU over traversal? — it shines when connectivity merges or repeated same-set checks arrive online.

Additional notes:

Near O(α(n)) per op ≈ O(1).

Interview script

"I first confirm the matrix represents undirected connectivity and I only need the number of connected groups. I start with brute force DFS or BFS over the matrix, which is O(n²) time and O(n) space. I optimize for repeated connectivity work with DSU path compression and union by rank, giving near O(1) amortized operations after scanning the O(n²) matrix."

Common Trap

Union without rank/size. Example: union(1,2), union(2,3), union(3,4)... chains linearly if you always attach the same way → find(1) walks all n nodes. Union by rank (attach shorter to taller) keeps the tree flat.

Execution Trace · Trap

Union without rank/size

BuggyInput: find(1)

union(1,2), union(2,3), union(3,4)... chains linearly if you always attach the same way → 'find(1)' walks all n nodes. Union **by rank** (attach shorter to taller) keeps the tree flat.

1 / 2

Pattern Connection

DSU is the engine for Number of Provinces, Accounts Merge (union by shared email), Redundant Connection (the edge that first connects an already-connected pair), and Kruskal's MST. A union that returns false in an undirected graph means you just closed a cycle.

Same pattern, new tweaks

"Merge things and ask 'are these two in the same group?' in near-O(1)":

Variation	The one thing that changes	Time
Number of Provinces	union adjacent friends; the answer is the count of distinct roots	—
Accounts Merge	union accounts that share any email, then group emails by root	—
Redundant Connection	the answer is the first edge whose two endpoints are already connected	—
Number of Islands II	online — union each newly added land cell with its neighbours, tracking the component count	—
Most Stones Removed	union stones sharing a row or column; removable = total − components	—

Minimum Spanning Tree — Kruskal + Union-Find Medium

↗ LeetCode: Min Cost to Connect All Points

Mark as solved

Problem

Given points on a plane, connect all of them with minimum total cost, where an edge's cost is the Manhattan distance — i.e. build a minimum spanning tree.

Constraints: 1 ≤ n ≤ 1000.

Example 1: choosing the cheapest cycle-free edges (e.g. weights 2,3,4,5) → their sum.

Example 2: points = [[3,12],[-2,5],[-4,1]] → 18 for the minimum Manhattan connection cost.

Solution — brute force

Brute force would try combinations of edges until it finds a connected cycle-free set of V-1 edges with minimum total weight. That is exponential in the number of edges and only useful as a correctness definition. Kruskal's optimization sorts edges by weight and uses Union-Find to accept exactly the cheapest edges that connect different components, relying on the cut property instead of enumerating trees.

best = infinity
for each subset of edges with V - 1 edges:
    if the subset connects all vertices and has no cycle:
        best = min(best, total weight)
return best

Brute force complexity: exponential in E because it enumerates candidate spanning trees.

Solution — optimized

Sort edges ascending; add an edge iff it joins two different components (no cycle). Union-Find tests connectivity in near-O(1).

Invariant

The chosen edges always form a forest; adding the globally-cheapest cross-component edge is safe (cut property).

Java

int minCostMST(int n, int[][] edges) {                // edges: {u, v, w}
    Arrays.sort(edges, (a, b) -> a[2] - b[2]);
    DSU dsu = new DSU(n);
    int cost = 0, used = 0;
    for (int[] e : edges) {
        if (dsu.union(e[0], e[1])) { cost += e[2]; if (++used == n - 1) break; }
    }
    return used == n - 1 ? cost : -1;                 // -1 if disconnected
}

Trace it

points where the cheapest edges are 2, 3, 4, 5. Kruskal adds them cheapest-first, skipping any edge whose two endpoints are already connected, until all points form one tree.

Execution Trace

Kruskal MST — edges sorted by weight

Step 1 / 4add cheapest edge

Time Complexity

Time O(E log E). Sorting edges dominates; DSU checks are near O(1) amortized.

Space Complexity

Space O(V) for DSU state, assuming the edge list is already materialized.

Learning notes

• Why sort edges by weight? — Kruskal must consider the cheapest safe edge first.
• Why call dsu.union before adding cost? — a false return means the edge would create a cycle.
• Why stop at n - 1 edges? — any connected tree on n vertices has exactly n−1 edges.
• Why return -1 if not enough edges were used? — the graph was disconnected.
• Why Union-Find here? — it answers “already connected?” fast while the forest grows.
• Why the cut property matters? — the cheapest edge crossing any component cut is safe to add.

Additional notes:

Time O(E log E) · Space O(V).

Interview script

"I first confirm the graph is undirected and I need the minimum-cost way to connect all vertices. I start with brute force by enumerating possible spanning trees, which is exponential in the edge count. I optimize with Kruskal: sort edges and use DSU to skip cycles, giving O(E log E) time and O(V) space."

Pattern Connection

Min Cost to Connect All Points (build a complete graph of Manhattan distances, then Kruskal/Prim). Prim (grow one tree with a min-heap) is the alternative, better on dense graphs.

Common Trap

Adding before union-check. Example: edges [(A,B,1),(B,C,2),(A,C,3)]. After adding the first two, A-B-C are connected. If you add (A,C,3) without find(A) != find(C), you form a cycle and inflate the total. Trust union's return.

Execution Trace · Trap

Adding before union-check

BuggyInput: [(A,B,1),(B,C,2),(A,C,3)]

edges '[(A,B,1),(B,C,2),(A,C,3)]'. After adding the first two, A-B-C are connected. If you add '(A,C,3)' without 'find(A) != find(C)', you form a cycle and inflate the total. Trust 'union''s return.

1 / 2

Same pattern, new tweaks

"Add the cheapest edge that joins two components" (Kruskal) or "grow one tree by its cheapest border edge" (Prim):

Variation	The one thing that changes	Time
Min Cost to Connect All Points	the graph is implicit — every pair of points is an edge weighted by Manhattan distance	—
Connecting Cities With Minimum Cost	plain Kruskal on the given edge list; return −1 if it stays disconnected	—
Optimize Water Distribution in a Village	model each well as an edge from a virtual node 0, then run MST	—
Find Critical and Pseudo-Critical Edges	rerun MST forcing each edge in / leaving it out to classify it	—

---

Check your understanding

🔗 Related patterns

• GraphsDynamic connectivity queries
• MSTKruskal uses union-find
• BFSAlternative for static connectivity