What it is
Union-find (disjoint set union) maintains a partition of elements into groups and supports two operations cheaply, even after many merges: find (which group is this element in?) and union (merge two groups). With path compression and union by size or rank, both run in near-constant amortized time. It's the right structure whenever the question is fundamentally about connectivity that builds up incrementally — you process a stream of relationships and need to know, at any point, whether two things are already linked — rather than about paths, distances, or ordering.
When it applies
- Elements arrive or merge one relationship at a time (edges, shared emails, shared endpoints), and you repeatedly need "are these two already connected?"
- You need to detect the specific edge or event that first connects two previously separate groups (a cycle-closing edge, a merge that joins two islands).
- Counting connected components as the structure grows incrementally is cheaper with union-find than re-running a full traversal after every update.
- If the question instead needs shortest paths, traversal order, or directed reachability, plain BFS/DFS is the better fit — union-find only answers "same group," it has no notion of distance or direction.
Tells in the problem
- "Return the edge that closes the cycle" or "the first time two things become connected" — the answer is the specific union call that finds both endpoints already sharing a root.
- Objects connected transitively through a shared attribute (two accounts are the same person if they share any one email, and that relation chains) — union each shared attribute's owners together.
- Repeated updates to a grid or graph (turn a cell into land, add an edge) with a query after every update for the number of connected pieces — incremental unions beat re-scanning the whole structure each time.
- A count of edges compared against a count of nodes, alongside "is this connected and acyclic" — the classic tree-validity check, answerable by counting successful unions.
- No weights, no direction, just "belongs to the same set as."
The classic mistake
The mistake interviewers commonly report is implementing find without path compression (or union without joining by size/rank), which still produces correct answers on small examples but degrades toward O(n) per operation as chains of parent pointers grow long — turning an intended near-linear solution into a quadratic one that times out only at scale. It happens because a naive union-find (plain parent array, no compression) passes every hand-traced example just as well as the optimized version, so the missing optimization is invisible until the input size in the constraints is taken seriously. State explicitly, before coding, that find will compress paths on the way up and that union will attach the smaller tree under the larger one's root — treat these as required parts of the structure, not optional polish.
Questions to start with
- Graph Valid Tree — the cleanest introduction: union each edge, and a union that fails (both endpoints already share a root) means a cycle.
- Number of Connected Components in an Undirected Graph — counting groups directly, decrementing a running count on every successful union.
- Redundant Connection — asks specifically for the edge that closes the cycle, which is exactly the first failed union in edge order.
- Accounts Merge — unions built from a shared attribute (email) rather than an explicit edge list, then grouped by root.
- Number of Islands II — the incremental case: land cells arrive one at a time and you must report the live component count after each one.