Intermediate LevelData Structures & Algorithms
What is Union-Find (Disjoint Set Union) and how do Path Compression and Union by Rank work?
ā Interview Prompt: Explain Union-Find data structure, Find, Union operations, path compression, union by rank, and near-O(1) amortised complexity.
Union-Find (DSU) maintains a collection of disjoint sets and supports:
ā¢
Find(x): Returns the root/representative of x's set.
ā¢
Union(x, y): Merges the sets containing x and y.
Optimisations:
ā¢
Path Compression: During Find, redirect every node directly to the root, flattening the tree.
ā¢
Union by Rank: Attach the shorter tree under the taller one to keep height logarithmic.
Complexity with both optimisations: $O(\alpha(N))$ amortised ā $O(1)$ practically.
Use Cases: Cycle detection, Kruskal's MST, connected components, social network grouping.
Code Implementation Example
typescript
class UnionFind {
private parent: number[];
private rank: number[];
constructor(n: number) {
this.parent = Array.from({ length: n }, (_, i) => i);
this.rank = new Array(n).fill(0);
}
find(x: number): number {
if (this.parent[x] !== x)
this.parent[x] = this.find(this.parent[x]); // path compression
return this.parent[x];
}
union(x: number, y: number): boolean {
const px = this.find(x), py = this.find(y);
if (px === py) return false; // already connected ā cycle!
// Union by rank
if (this.rank[px] < this.rank[py]) this.parent[px] = py;
else if (this.rank[px] > this.rank[py]) this.parent[py] = px;
else { this.parent[py] = px; this.rank[px]++; }
return true;
}
}š”Union-Find with path compression and union by rank ā near-O(1) operations.
šÆ Interview Key Takeaway
Union-Find with path compression + union by rank achieves O(Ī±(N)) amortised ā nearly O(1). Essential for Kruskal's MST and cycle detection.
#DSA#Union Find#Disjoint Set#Graph#Intermediate
Back to all Data Structures & Algorithms Questionsā