Union-Find (Disjoint Set)
Week 10
What it is
Tracks which elements belong to the same connected component. Supports two operations in near O(1) amortized.
class UnionFind {
constructor(n) {
this.parent = Array.from({length: n}, (_, i) => i);
this.rank = Array(n).fill(0);
this.components = n;
}
find(x) {
if (this.parent[x] !== x)
this.parent[x] = this.find(this.parent[x]); // path compression
return this.parent[x];
}
union(x, y) {
const px = this.find(x), py = this.find(y);
if (px === py) return false;
// 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]++; }
this.components--;
return true;
}
connected(x, y) { return this.find(x) === this.find(y); }
}| Operation | Complexity (with path compression + rank) |
|---|---|
| find | O(α(n)) ≈ O(1) |
| union | O(α(n)) ≈ O(1) |
Key Problems
| # | Problem | Pattern | Difficulty |
|---|---|---|---|
| 1 | Number of Connected Components | Union-Find | Medium |
| 2 | Redundant Connection | Cycle detection | Medium |
| 3 | Accounts Merge | Union-Find | Medium |
| 4 | Number of Islands II | Dynamic union-find | Hard |
| 5 | Minimum Spanning Tree (Kruskal) | Sort edges + UF | Medium |
Real-World Frontend Application
Union-Find is fantastic for determining connectivity. On the frontend, this can be used in graphics applications (like a paint bucket "flood fill" tool grouping connected pixels of the same color) or analyzing social network graphs dynamically.
Union Find (Disjoint Set Array)
1 / 4
0
[0]
1
[1]
2
[2]
3
[3]
Initially, every element is its own parent (roots of their own sets).