Union-Find (Disjoint Set Union) for Coding Interviews
4 views
Union-Find, also called Disjoint Set Union (DSU), is a small data structure that quietly solves a whole class of graph problems. It shows up in interviews whenever you need to group items into connected components and answer "are these two in the same group?" quickly. Once you can write it from memory in a few minutes, many medium and hard problems become routine.
What it does
DSU maintains a collection of disjoint sets and supports two operations:
- find(x): return the representative (root) of the set containing x.
- union(x, y): merge the sets containing x and y.
With two optimizations, each operation runs in nearly constant amortized time (the inverse Ackermann function, which is effectively at most 4 for any realistic input).
The implementation
Store a parent array where parent[i] = i initially, plus a rank or size array.
find(x): while parent[x] != x, move up. Add path compression: after finding the root, point every node along the path directly to the root (recursively, parent[x] = find(parent[x])).
union(x, y): find both roots; if they are equal, the elements are already connected (return false, which is useful for cycle detection). Otherwise attach the smaller tree under the larger one (union by size or rank) and return true.
That is about 15 lines in any language. Practice writing it until it is automatic.
Problems where DSU shines
1. Number of connected components in an undirected graph: union every edge, then count distinct roots, or start with n components and decrement on each successful union.
2. Redundant connection / detect a cycle: the first edge whose union returns false creates a cycle.
3. Graph valid tree: a graph with n nodes is a tree if it has exactly n - 1 edges and no union fails.
4. Number of islands II (online version): add land cells one by one and union with neighboring land; track the component count after each addition. BFS would be too slow here, which is why interviewers ask it.
5. Accounts merge: union accounts sharing an email, then group emails by root.
6. Kruskal's minimum spanning tree: sort edges by weight and add each edge if union succeeds.
7. Satisfiability of equality equations: union all "a==b" pairs, then check that no "a!=b" pair shares a root.
8. Smallest string with swaps: indices connected by swap pairs form groups; sort characters within each group.
DSU versus BFS/DFS
For a static graph, BFS or DFS also finds components in linear time, so either works. DSU wins when edges arrive incrementally, when you need repeated connectivity queries, or when you are building an MST. Mentioning this trade-off shows maturity.
Mapping non-integer keys
When elements are strings (like emails) or grid coordinates, map them to integer ids with a hash map, or flatten a grid cell (r, c) to r * cols + c.
Common mistakes
- Comparing x and y instead of their roots in union.
- Forgetting path compression and hitting worst-case chains.
- Counting components by scanning parent[i] == i before compressing everything, which is fine, but scanning parent values directly without find gives wrong answers.
How to present it
Say you will use Union-Find, briefly explain the two operations and their near-constant complexity, write the class, then apply it to the problem. Interviewers appreciate a clean, reusable helper.
Candidates who want live support while explaining such solutions can use Linkjob AI (https://linkjob.ai), which offers real-time help during job interviews and technical interviews.