DSA & Algorithms
Part 17 of 21 · DSA Interview PatternsUnion-Find (Disjoint Set Union) — Connectivity, Components & Kruskal
DSU with path compression and union-by-rank for dynamic connectivity.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
You merge groups and ask whether two items are connected
Prefer
Disjoint-set union
Almost O(1) per operation with compression and rank. The parent array is the whole structure.
- find flattens the path it walks.
- union attaches the lower rank under the higher rank.
- Kruskal is sort edges, then union the ends if they differ.
Alternative
Rebuild DFS components after every edge
Correct offline. Wasteful when the interviewer is streaming edges.
- Skipping compression and rank and then claiming inverse-Ackermann time.
- Off-by-one between 0-index and 1-index nodes.
- Ignoring the false return from union.
Find roots, then link
Same root means already connected. Different roots means you just merged.
- 1
Find both roots
Compression points nodes toward the root on the way. - 2
Same root
This edge is redundant. Do not decrement the part count. - 3
Different roots
Link lower rank under higher rank and lose one part.
Overview
DSU with path compression and union-by-rank for dynamic connectivity.
Below is the full pattern: when to reach for it, a top-down picture, runnable Python and TypeScript templates, complexity, traps, LeetCode drills, and Q&A.
When to use / recognition cues
Use DSU for dynamic connectivity: merge sets, query same-component, count components, Kruskal MST.
Recognition cues
- number of connected components / provinces
- redundant connection
- accounts merge
- earliest day to connect all
Mental model
Decisions
- 1
Step 1 union(a, b)
- nextStep 2 ra = find(a) with path compression
- 2
Step 2 ra = find(a) with path compression
- nextStep 3 rb = find(b) with path compression
- 3
Step 3 rb = find(b) with path compression
- nextStep 4 ra equals rb?
- ?
Step 4 ra equals rb?
- yesStep 5a Already connected - this edge would close a cycle
- noStep 5b Attach the lower-rank root under the higher-rank root
- 5
Step 5a Already connected - this edge would close a cycle
- 6
Step 5b Attach the lower-rank root under the higher-rank root
- nextStep 6 components -= 1
- no rank and no compressionFailure path - chains degrade find to O(n)
- 7
Step 6 components -= 1
- 8
Failure path - chains degrade find to O(n)
Lesson map
Union-Find (Disjoint Set Union) — Connectivity, Components & Kruskal
DSU with path compression and union-by-rank for dynamic connectivity.
Architecture. Step 1 union(a, b) Ready. Step 2 ra = find(a) with path compression Ready. Step 3 rb = find(b) with path compression Ready. Step 4 ra equals rb? Ready. Step 5a Already connected - this edge would close a cycle Ready. Step 5b Attach the lower-rank root under the higher-rank root Ready. Step 6 components -= 1 Ready. Failure path - chains degrade find to O(n) Ready
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB U["Step 1 union(a, b) Ready"] FA["Step 2 ra = find(a) with path compression Ready"] FB["Step 3 rb = find(b) with path compression Ready"] C["Step 4 ra equals rb? Ready"] S["Step 5a Already connected - this edge would close a cycle Ready"] L["Step 5b Attach the lower-rank root under the higher-rank root Ready"] R["Step 6 components -= 1 Ready"] F["Failure path - chains degrade find to O(n) Ready"] U -->|continues| FA FA -->|continues| FB FB -->|continues| C C -->|yes| S C -->|no| L L -->|continues| R L -->|no rank and no compression| F
Read the chart from top to bottom. Two-way decisions keep the card narrow on a phone.
Core template (Python)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Core template (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Complexity analysis
- Amortized O(alpha(n)) per op with path compression + union by rank (inverse Ackermann); a single op can still cost O(log n).
- Space O(n).
Common pitfalls & interview traps
LeetCode drill (real problems)
- Number of Provinces
- Redundant Connection
- Accounts Merge
- Graph Valid Tree
- Number of Islands
- Swim in Rising Water
- Similar String Groups
Go deeper
- Back to the pattern map.
- NeetCode roadmap
- CP-Algorithms
Interview Q&A
Path compression?
Answer
Point nodes to root while finding to flatten tree.
Union by rank?
Answer
Attach shallower tree under deeper to keep height small.
Redundant edge?
Answer
Edge whose ends already same component.
Valid tree?
Answer
n-1 edges and one component (or union always merges).
Vs DFS components?
Answer
DSU better when edges stream / online merges.
Kruskal?
Answer
Sort edges; union if different components; MST on a connected graph, minimum spanning forest otherwise.