Union-Find¶
Also known as: Disjoint Set Union (DSU), Union by Rank + Path Compression
Every element points to a "leader." To merge two groups, point one leader at the other. To ask "are these two connected?", follow both to their leaders and compare. Path compression flattens the chains as you go, so the structure gets faster the more you use it.
Before you start¶
What 'solved properly' looks like
Target: Effectively O(1) amortised per operation with both optimisations. If your solution is slower than that, you've found a solution but not this pattern — the judge says "Accepted" either way, so treat this as your real benchmark.
The idea¶
Each element starts as its own group, pointing to itself. When you union two elements, you find their roots (leaders) and make one point to the other — optionally using rank to keep the tree shallow. When you find an element's root, you compress the path by making every node on the way point directly to the root. These two optimisations together make the structure nearly constant-time per operation.
Why it matters: Union-find is the best tool for dynamic connectivity — when edges arrive one at a time and you need to answer connectivity queries as you go. It's also the engine behind Kruskal's MST algorithm, and it's surprisingly simple once you see the array-based representation.
When to reach for it¶
Reach for it for dynamic connectivity (edges arriving over time), counting connected components in an undirected graph, detecting cycles in an undirected graph, grouping equivalent things, or Kruskal's minimum spanning tree.
When not to use it
On a static graph, plain DFS/BFS finds components more simply — DSU earns its keep when connections arrive incrementally and you must answer queries as you go. Skip path compression and the whole structure degrades to a linked list, which is the classic way to implement it correctly and still be slow.
Practice set¶
Work these top to bottom. The time-box is a cue to pause and re-read the triggers above if you're still stuck when it passes — not a deadline to race. Getting unstuck by stepping back is the skill being trained.
| # | Problem | Where | Difficulty | Time-box | Role |
|---|---|---|---|---|---|
| 1 | Number of Provinces | LeetCode | Medium | 20 mins | teaching |
| 2 | Redundant Connection | LeetCode | Medium | 25 mins | teaching |
| 3 | Most Stones Removed with Same Row or Column | LeetCode | Medium | 30 mins | consolidation |
| 4 | Satisfiability of Equality Equations | LeetCode | Medium | 25 mins | consolidation |
| 5 | Accounts Merge | LeetCode | Medium | 35 mins | challenge |
Already know this? Test out.
If you can solve Accounts Merge cleanly in one sitting — using union-find to group accounts by email — you already own this pattern, so move on to the next one. If it tangles you up, that's your signal to work the set from the top instead of skipping.