Union-Find
Intermediate · 16 min read · Problem-Solving Patterns, Graphs
Group things that are connected, fast — with path compression.
Some problems are only about one question, asked over and over while connections keep being added: "are these two things in the same group?" You could run a BFS each time — O(n) per question.
The idea: every group has a representative
Each element points to a parent; following parents leads to the group's root — its representative. Two elements are connected exactly when they have the same root.
The template (memorise this)
Two optimisations make it fast:
Worked problems
Add edges one by one; the first edge whose endpoints are already connected creates the cycle.
Union-Find or BFS/DFS?
Practice ladder
Interview questions
- What is the complexity of Union-Find with path compression and union by size?
- How do you detect a cycle in an undirected graph with Union-Find?
Further reading
Key takeaways
- Union-Find tracks groups: find returns a representative, union merges two groups.
- Union by size + path compression → effectively O(1) per operation.
- union returning false means "already connected" — a built-in cycle detector for undirected graphs.
- Best when edges arrive over time or only group membership matters; Kruskal's MST is Union-Find plus sorting.
- Compare roots, never parents.