The beautiful part: neither trick complicates the code much, yet together they're provably near-optimal. This is the version you should always write in interviews.
Rank is an upper bound on a tree's height. On union, attach the lower-rank root under the higher-rank root; ranks equal → pick either and increment its rank by one. This alone bounds height at O(log n).
During find(x), after locating the root, re-point every node on the path directly to the root. Future finds on those nodes are O(1). The one-liner recursive form parent[x] = find(parent[x]) does this elegantly.
| Optimizations | Amortized per op |
|---|---|
| Neither (Day 8) | O(n) |
| Union by rank only | O(log n) |
| Path compression only | O(log n) amortized |
| Both | O(α(n)) ≈ O(1) |
Union by rank + path compression. Also tracking component count and sizes.
public class UnionFind {
private final int[] parent, rank, size;
private int count; // number of disjoint sets
public UnionFind(int n) {
parent = new int[n];
rank = new int[n];
size = new int[n];
count = n;
for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
}
/** find with path compression (recursive one-liner). */
public int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]); // flatten path
return parent[x];
}
/** union by rank; returns false if already merged. */
public boolean union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return false;
if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; } // ra = taller
parent[rb] = ra; // attach shorter under taller
size[ra] += size[rb];
if (rank[ra] == rank[rb]) rank[ra]++; // tie → height grows by 1
count--;
return true;
}
public boolean connected(int a, int b) { return find(a) == find(b); }
public int componentCount() { return count; }
public int componentSize(int x) { return size[find(x)]; }
}
ra is the surviving root — add the child's size to it, not the other way.Once inputs get large or ask for component sizes / counts on the fly, the optimized DSU (with size tracking) is what makes these tractable:
| Disguise / phrasing | What's really asked | Twist to handle |
|---|---|---|
| "Redundant connection / extra edge" | First edge joining an existing set | union returns false → that's the answer |
| "Min operations to connect network" | components − 1 vs spare edges | Need componentCount(); count redundant edges |
| "Largest component / group size" | Max subtree size | Track size[]; query componentSize(root) |
| "Number of islands as land is added" | Incremental component count | Decrement count on each successful union (Day 10) |
| "n up to 10⁵–10⁶, many unions/finds" | Performance | MUST have rank + path compression → O(α(n)) |
| "% of population in largest friend group" | Size-weighted query | Union by size doubles as the size counter |