Union-find keeps items in groups and answers whether two items share a group. Interviewers expect find with path compression, union by size or rank, and the cost: nearly O(1) amortized per operation, formally O(α(n)). The signal is connectivity that grows as edges arrive, or counting groups while they merge.
Operations and what they cost
It is also called a disjoint set union. Each group is a small tree of parent pointers, and the root names the group. The optimizations are the whole story, because without them it can be as slow as a linked list.
| Version | find | union | Space |
|---|---|---|---|
| No optimizations | O(n) at worst | O(n) at worst | O(n) |
| Union by size or rank alone | O(log n) | O(log n) | O(n) |
| Path compression alone | O(log n) amortized | O(log n) amortized | O(n) |
| Both | O(α(n)) amortized | O(α(n)) amortized | O(n) |
α(n) is the inverse Ackermann function, which grows so slowly that it is at most 4 for any input you could ever store. Saying "nearly constant, amortized" is accurate, and naming α(n) if asked is enough. Processing E edges over V nodes therefore costs about O(E α(V)) time and O(V) space.
When to reach for it
- The question is only whether two things are connected, and edges keep arriving over time.
- You need to count groups as they merge: friend circles, accounts that share an email.
- You need to know whether a new edge would close a cycle in an undirected graph.
- You are building a minimum spanning tree with Kruskal's algorithm, which sorts edges and adds those that join two groups.
Reach for BFS or DFS instead when you need the path itself or the number of steps, because union-find only knows the group. It also cannot split a group, so it does not suit edges being removed.
A short trace
Five items, 0 to 4, each starting as its own group. Union by size attaches the smaller root under the larger, and ties attach the second root under the first. Path compression shows up in the last step.
Start parent = [0, 1, 2, 3, 4] 5 groups
union(0, 1) parent = [0, 0, 2, 3, 4] 1 goes under 0, 4 groups
union(2, 3) parent = [0, 0, 2, 2, 4] 3 goes under 2, 3 groups
union(1, 3) parent = [0, 0, 0, 2, 4] roots 0 and 2, same size: 2 goes under 0, 2 groups
find(3) parent = [0, 0, 0, 0, 4] 3 -> 2 -> 0, so 3 now points straight at 0The last line is the point. The first find(3) walks two links, and every later one walks one. That is what keeps the trees flat.
How it looks in Python, JavaScript and Java
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
self.groups = n
def find(self, x):
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # halve the path
x = self.parent[x]
return x
def union(self, a, b):
"""Returns False if a and b were already in one group."""
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False
if self.size[ra] < self.size[rb]:
ra, rb = rb, ra
self.parent[rb] = ra # smaller group under larger
self.size[ra] += self.size[rb]
self.groups -= 1
return TrueJavaScript
class UnionFind {
constructor(n) {
this.parent = Array.from({ length: n }, (_, i) => i);
this.size = new Array(n).fill(1);
this.groups = n;
}
find(x) {
while (this.parent[x] !== x) {
this.parent[x] = this.parent[this.parent[x]];
x = this.parent[x];
}
return x;
}
union(a, b) {
let ra = this.find(a);
let rb = this.find(b);
if (ra === rb) return false;
if (this.size[ra] < this.size[rb]) [ra, rb] = [rb, ra];
this.parent[rb] = ra;
this.size[ra] += this.size[rb];
this.groups--;
return true;
}
}Java
class UnionFind {
private final int[] parent;
private final int[] size;
int groups;
UnionFind(int n) {
parent = new int[n];
size = new int[n];
groups = n;
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
boolean union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return false;
if (size[ra] < size[rb]) {
int t = ra;
ra = rb;
rb = t;
}
parent[rb] = ra;
size[ra] += size[rb];
groups--;
return true;
}
}These use path halving, a one-line form of path compression that points each visited node at its grandparent. It has the same bound, and needs no recursion, so a long chain cannot hit a recursion limit.
How to explain the choice out loud
I only need to know whether two accounts are connected, and links keep arriving, so re-running a search each time would be wasteful. I'll use union-find: each group is a tree, and two items are connected if they share a root. With union by size and path compression, each operation is nearly constant, O(alpha of n) amortized, so E links cost about O(E) time and O(V) space. If I needed the actual path between two accounts, I'd switch to a BFS, because union-find doesn't keep it.
Common mistakes
- Comparing parents instead of roots:
parent[a] == parent[b]misses items lower in the tree. - Updating the wrong root in union, such as setting
parent[a]whenais not a root. - Leaving out both optimizations, then claiming nearly constant time.
- Using it when the question needs the path or the distance, which it does not record.
- Writing find recursively on very deep trees in Python, which can hit the recursion limit before compression helps.
Where to go next
- Patterns: graph patterns, and the graph data structure for how to store one.
- Worked problem: no worked problem uses union-find yet. The closest is Degrees of Separation Between Members, a connectivity question that needs distance, so it shows when to choose a search instead.
- All the figures in one place: the Big O cheat sheet.
- Practice saying it: a coding mock interview.