Originally published on LeetCopilot Blog
DSU solves connectivity fast, but parent updates feel invisible. This dry run shows each find and union step by step.
Disjoint set union (DSU) solves connectivity questions fast, but the parent updates can feel invisible. This dry run illustrates each find and union with path compression so you can narrate the structure clearly in interviews.
TL;DR
- Topic: Disjoint set union with path compression and union by rank.
- Interview value: Guarantees near-constant amortized operations and demonstrates data structure rigor.
- Core steps: initialize parents, find with compression, union by rank, answer queries.
- Beginners often skip rank updates, for…
Originally published on LeetCopilot Blog
DSU solves connectivity fast, but parent updates feel invisible. This dry run shows each find and union step by step.
Disjoint set union (DSU) solves connectivity questions fast, but the parent updates can feel invisible. This dry run illustrates each find and union with path compression so you can narrate the structure clearly in interviews.
TL;DR
- Topic: Disjoint set union with path compression and union by rank.
- Interview value: Guarantees near-constant amortized operations and demonstrates data structure rigor.
- Core steps: initialize parents, find with compression, union by rank, answer queries.
- Beginners often skip rank updates, forget to attach smaller trees, or miss compressing during find.
- You’ll get a diagram-friendly walkthrough, TypeScript code, prep drills, and pitfalls to avoid.
Beginner-Friendly Explanations
The Forest Mental Model
Think of each node pointing to a parent; roots point to themselves. Compression flattens paths so future finds walk fewer edges, aligning with the sliding window learning path.
Why Union by Rank Matters
Attaching the smaller tree under the larger keeps height small. Without it, compression alone can still leave skewed trees that slow repeated queries.
How Path Compression Feels in Practice
During find(x), you recursively reach the root, then rewrite parent[x] to that root on the way back. This "shortcut" is the secret to almost O(1) queries.
Step-by-Step Learning Guidance
1) Initialize Parents and Rank
Create parent[i] = i and rank[i] = 1 for all nodes. Handle empty inputs and single-node cases first, habits consistent with the interview communication guide.
2) Implement find with Compression
When find(x) recurses, set parent[x] = find(parent[x]) to flatten the path. This keeps future queries quick.
3) Implement union by Rank
Find roots of a and b. If equal, do nothing. Otherwise attach the lower-rank root under the higher. If ranks tie, pick one root, attach, and increment its rank.
4) Narrate While Dry Running
For edges (0,1), (1,2), (3,4), say out loud: "connect 0-1 -> roots 0 and 1, attach 1 under 0; connect 1-2 -> roots 0 and 2, attach 2 under 0." This narration prepares you for a mock interview routine.
5) Verify Connectivity Queries
Answer find(x) == find(y) for pairs like (0,2) or (2,3). After compression, parents should point directly to roots.
Visualizable Example: DSU in TypeScript
class DSU {
parent: number[];
rank: number[];
constructor(n: number) {
this.parent = Array.from({ length: n }, (_, i) => i);
this.rank = Array(n).fill(1);
}
find(x: number): number {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]);
}
return this.parent[x];
}
union(a: number, b: number): void {
const rootA = this.find(a);
const rootB = this.find(b);
if (rootA === rootB) return;
if (this.rank[rootA] < this.rank[rootB]) {
this.parent[rootA] = rootB;
} else if (this.rank[rootA] > this.rank[rootB]) {
this.parent[rootB] = rootA;
} else {
this.parent[rootB] = rootA;
this.rank[rootA]++;
}
}
}
Trace the parents after unions (0,1), (1,2), (3,4), (2,4). You should see all nodes compressed under a single root.
Practical Preparation Strategies
Draw Parents After Every Operation
Record parent arrays after each union. This visualization trains you to spot whether compression actually shortened paths.
Mix Query Orders
Interleave finds and unions to mimic interview follow-ups. This strengthens muscle memory for when compression triggers.
Compare With and Without Compression
Run the same sequence with compression commented out. Observe the deeper trees and slower reasoning; this contrast sticks, especially when using the AI prep primer.
Light Guidance Only When Needed
Tools like LeetCopilot can point out missed rank bumps without revealing the entire solution, keeping your reasoning intact.
Common Mistakes to Avoid
Forgetting to Return the Root in find
If find doesn’t return the compressed root, unions may attach wrong parents.
Skipping Rank Updates
Without rank bumps on ties, future unions might favor already larger trees incorrectly.
Compressing Only Sometimes
Always compress on find; partial compression leaves inconsistent depths that complicate debugging.
Assuming 1-Indexed Nodes
If the input uses 0-indexing, offset mistakes break connectivity checks. Confirm indexing early.
FAQ
How do I know compression worked?
After a find call, parent[x] should equal the ultimate root; printing the parent array after queries helps verify.
What should I practice before DSU?
Be comfortable with arrays, recursion, and simple graph representations.
Is DSU important for interviews?
Yes—it’s common in graph connectivity, Kruskal’s MST, and grouping problems.
Can I skip union by rank if I compress paths?
You can, but rank keeps trees shallow even before many queries run, improving consistency.
Conclusion
Union-find with path compression rewards careful narration: initialize cleanly, compress on every find, and attach by rank. With steady dry runs and small diagrams, you’ll answer connectivity questions confidently without hand-waving.
If you’re looking for an AI assistant to help you master LeetCode patterns and prepare for coding interviews, check out LeetCopilot.