Union-Find (Disjoint Set Union) for Coding Interviews: A Practical Guide

Union-Find, also called Disjoint Set Union (DSU), is one of those data structures that rarely shows up in day-to-day product code but appears again and again in coding interviews. Once you recognize the pattern, a whole family of "connected components" problems collapses into a few lines of code. This guide covers how it works, the two optimizations interviewers expect you to know, and the problem shapes where it shines. What problem does it solve? Union-Find keeps track of elements partitioned into groups. It supports two operations: - find(x): return the representative (root) of the group containing x. - union(a, b): merge the groups containing a and b. If find(a) == find(b), the two elements are connected. That is all you need for questions like "how many friend circles are there?", "does adding this edge create a cycle?", or "are these two accounts the same person?" The minimal implementation parent = list(range(n)) rank = [0] * n def find(x): while parent[x] != x: parent[x] = parent[parent[x]] # path halving x = parent[x] return x def union(a, b): ra, rb = find(a), find(b) if ra == rb: return False # already connected if rank[ra] < rank[rb]: ra, rb = rb, ra parent[rb] = ra if rank[ra] == rank[rb]: rank[ra] += 1 return True The two optimizations to mention out loud 1. Path compression (or path halving as above): every find flattens the tree so future lookups are nearly constant time. 2. Union by rank or size: always attach the smaller tree under the larger one, so trees stay shallow. Together they give an amortized cost of O(alpha(n)) per operation, where alpha is the inverse Ackermann function, which is effectively constant for any realistic input. Saying this clearly, and explaining why each optimization matters, is often worth more points than the code itself. Classic interview problems - Number of connected components in an undirected graph: union every edge, then count distinct roots. - Redundant connection / cycle detection: the first edge where union returns False is the one that closes a cycle. - Accounts merge: map each email to an id, union emails that share an account, then group by root. - Kruskal's minimum spanning tree: sort edges by weight and union them, skipping edges whose endpoints are already connected. - Number of islands II (dynamic grid): add land cells one at a time and union with neighbors, tracking the component count as you go. When NOT to use it Union-Find answers "are these connected?" but not "what is the path between them?" If the problem needs shortest paths, ordering, or the ability to split groups apart, reach for BFS/DFS or another structure. Interviewers like candidates who can explain that trade-off. How to practice Write the structure from memory until it takes under two minutes, then solve five or six problems using the same template. Talk through complexity each time. Many candidates know the idea but stumble when nerves hit and they have to explain path compression in real time. That live-explanation moment is exactly where Linkjob AI (https://linkjob.ai) can help: it provides real-time help during job interviews and technical interviews, so you can keep your reasoning structured while you code. Use it alongside solid practice, not instead of it. Key takeaway: if a problem talks about grouping, merging, or connectivity without needing actual paths, think Union-Find first.