Module A-3 — Union-Find: Path Compression and Union by Rank
What this module covers: Every structure so far answers "what's the smallest/largest" or "how do I traverse this." Union-Find answers a different question entirely: are these two things connected, directly or transitively? This module covers the naive approach's hidden O(n) cost, and the two independent optimizations — path compression and union by rank — that together make Union-Find's operations run in almost constant time.
The Question: Connectivity, Not Order
Given a set of elements, some of which are connected to each other (directly or through a chain of connections), Union-Find answers two operations efficiently: find(x) — which connected group does x belong to? — and union(x, y) — merge x's group and y's group into one. Neither operation cares about ordering values or finding a maximum; it only cares about group membership.
The Naive Approach's Hidden Cost
The obvious implementation: an array mapping each element to its current group ID.
typescript
find is O(1) here, which looks great — but union has to relabel every single element currently in one of the two groups being merged, an O(n) scan in the worst case. Merging groups repeatedly (which is the entire point of Union-Find) means paying that O(n) cost on every single union — for n unions, that's O(n²) overall, the same quadratic trap flagged repeatedly throughout this course.
The Tree-Based Fix: Point to a Parent, Not a Group Label
Instead of storing a group label, store a parent pointer for each element — following parent pointers upward eventually reaches a root, which serves as that group's representative identity. union becomes cheap: just attach one root under the other, no relabeling of every member required.
typescript
This trades the naive approach's cost around: union is now cheap (find the two roots, attach one), but find can be expensive — if trees are allowed to grow into long chains (attaching root Y under root X repeatedly, always the same direction, can produce a straight-line tree), find degenerates to O(n), the exact same degeneration risk flagged for BSTs in Module P-5 and quicksort in Module P-10: a strategy that's efficient in general can become linear-chain-like under specific, unlucky sequences of operations.
Optimization 1: Path Compression
While walking up to find the root, re-point every node visited directly to the root, flattening the tree for every future find call on any of those nodes:
typescript
The recursive call finds the true root; the assignment afterward re-parents x (and, because of the recursion, every node along the original path) directly to that root, instead of leaving the original chain of intermediate parents in place. The next find call on any of those nodes is now O(1) instead of walking the original chain — this is a genuinely self-improving structure: every find call makes future find calls on the same nodes cheaper, a flattening effect that compounds across repeated use.
Optimization 2: Union by Rank
Path compression alone helps, but combining it with a rule for which root gets attached under which during union is what gives the strongest guarantee: always attach the shorter tree under the taller one's root, tracked with a rank (an upper bound on tree height):
typescript
Union by rank on its own already bounds tree height to O(log n) — attaching short under tall specifically prevents the long-chain degeneration the naive tree-based approach was vulnerable to. Combined with path compression, the two optimizations reinforce each other: path compression keeps flattening trees that union by rank keeps from growing too tall in the first place. Together, this gives amortized time per operation that's so close to constant it's described using the inverse Ackermann function, α(n) — a function that grows so slowly it's effectively ≤ 4 or 5 for any input size that could ever actually occur in practice, even far beyond the number of atoms in the observable universe. The honest, practical takeaway: with both optimizations, treat Union-Find operations as O(1) — the theoretical function is a mathematical nicety, not something that meaningfully differs from constant time at any realistic scale.
Where This Shows Up in Your Stack
Social network friend-group detection: "are these two users in the same connected friend cluster" is a direct find(x) === find(y) check, and "these two users just became friends, merge their clusters" is union(x, y) — exactly this structure, applied to a live social graph.
Account merging (a user signs up with two different emails that turn out to belong to the same person, or a fraud-detection system linking accounts sharing a phone number or device fingerprint) is a repeated union operation across pairs of related identifiers, with find used afterward to answer "which merged identity does this account ultimately belong to."
Redundant connection / cycle detection in an undirected graph: attempting to union two nodes that find already shows are in the same group means the edge connecting them would create a cycle — a direct, O(1)-per-edge alternative to running a full DFS (Module A-4) or BFS (Module A-5) for this specific check.
Kruskal's algorithm for building a minimum spanning tree (considering edges from cheapest to most expensive, adding each one only if its two endpoints aren't already connected) uses exactly this cycle-detection property of Union-Find as its core mechanism, at every single edge considered.
Summary
Union-Find answers connectivity questions — same group or not — a fundamentally different question from ordering, searching, or traversal.
The naive group-label approach makes find O(1) but union O(n), since merging groups means relabeling every member of one group — O(n²) overall across many unions.
Representing each group as a tree (parent pointers, union attaches roots) fixes union's cost, but risks find degenerating to O(n) if trees are allowed to grow into long chains.
Path compression flattens every node visited during find directly to the root, making future lookups on those nodes cheaper — a self-improving structure.
Union by rank always attaches the shorter tree under the taller one, bounding tree height and preventing the long-chain degeneration risk on its own.
Combined, both optimizations reduce amortized cost per operation to effectively O(1) in practice (formally O(α(n)), a function that never meaningfully exceeds a small constant at any realistic scale).
The next module, Graph Traversal: Depth-First Search (DFS), covers the first general-purpose graph traversal algorithm — visiting every reachable node from a starting point, the foundation both Modules A-5 through A-9 and this module's cycle-detection alternative build on.
Knowledge Check
Why does the naive group-label approach (groupId array) make union an O(n) operation, even though find is O(1)?
What specific effect does path compression have on the tree structure during a find call, and why does the module describe this as "self-improving"?
According to the module, why does combining path compression with union by rank yield a stronger practical guarantee than either optimization alone?
Test your knowledge with more question sets
Sign in to access a wider variety of questions and get notified when new practice sets are added to this module.
// Naive: groupId[x] tells you which group x currently belongs tofunctionfindNaive(groupId:number[], x:number):number{return groupId[x];// O(1) — direct lookup}functionunionNaive(groupId:number[], x:number, y:number):void{const groupY = groupId[y];const groupX = groupId[x];for(let i =0; i < groupId.length; i++){if(groupId[i]=== groupY) groupId[i]= groupX;// relabel EVERY element in y's group}}
classUnionFind{private parent:number[];constructor(size:number){this.parent =Array.from({ length: size },(_, i)=> i);// every element starts as its own root}find(x:number):number{while(this.parent[x]!== x){ x =this.parent[x];// walk up toward the root}return x;}union(x:number, y:number):void{const rootX =this.find(x);const rootY =this.find(y);if(rootX !== rootY){this.parent[rootY]= rootX;// attach one tree under the other — O(1), no relabeling of members}}}
find(x:number):number{if(this.parent[x]!== x){this.parent[x]=this.find(this.parent[x]);// recursively find the root, then attach x directly to it}returnthis.parent[x];}
classUnionFind{private parent:number[];private rank:number[];constructor(size:number){this.parent =Array.from({ length: size },(_, i)=> i);this.rank =newArray(size).fill(0);}find(x:number):number{if(this.parent[x]!== x){this.parent[x]=this.find(this.parent[x]);// path compression}returnthis.parent[x];}union(x:number, y:number):void{const rootX =this.find(x);const rootY =this.find(y);if(rootX === rootY)return;// already in the same group// Attach the shorter tree under the taller tree's root — keeps the combined tree shallowif(this.rank[rootX]<this.rank[rootY]){this.parent[rootX]= rootY;}elseif(this.rank[rootX]>this.rank[rootY]){this.parent[rootY]= rootX;}else{this.parent[rootY]= rootX;this.rank[rootX]++;// only grows when merging two trees of EQUAL rank}}}