Coding interview pattern
Track connectivity between elements with near-constant-time union and find.
The idea
Union-Find (also called Disjoint Set Union) maintains a partition of elements into disjoint groups and answers two questions extremely fast: which group is this element in (find), and merge these two groups (union). Each element points to a parent; the representative of a group is the root of its tree. With two optimisations, path compression (flatten the tree during find) and union by rank or size (attach the smaller tree under the larger), both operations run in nearly constant amortised time.
It is the right tool whenever a problem is fundamentally about connectivity or grouping under a stream of merges: counting connected components, detecting whether adding an edge creates a cycle in an undirected graph, or grouping items that share an attribute transitively (accounts merge, friend circles, equations equality). Where DFS or BFS recomputes connectivity from scratch, union-find answers it incrementally as edges arrive.
Union-Find also underpins Kruskal's minimum spanning tree algorithm, where you add edges in increasing weight and use union-find to skip any edge whose endpoints are already connected. The implementation is short: a parent array, a find with path compression, and a union that links roots by rank. That compactness, combined with its speed, makes it a favourite for grid and graph grouping problems.
Recognition
Cost
| Operation | Time | Space |
|---|---|---|
| Find (with path compression) | O(alpha(n)) ~ O(1) | O(n) |
| Union (by rank/size) | O(alpha(n)) ~ O(1) | O(n) |
| m operations on n elements | O(m * alpha(n)) | O(n) |
Worked example
Translatable skeleton
Language-agnostic on purpose. Translate it to your language of choice.
parent = list(range(n)); def find(x): while parent[x] != x: parent[x] = parent[parent[x]]; x = parent[x]; return x // union joins rootsPractice
Work these in order, easy to hard. Each is chosen to drill a different facet of the pattern.
| Problem | Level | Why it fits |
|---|---|---|
| Number of Connected Components | Medium | The template union-find problem. |
| Graph Valid Tree | Medium | Connected and exactly n-1 edges, no cycle. |
| Redundant Connection | Medium | The edge that first connects two already-joined nodes. |
| Accounts Merge | Medium | Union accounts sharing an email. |
| Number of Islands | Medium | Union adjacent land cells (alternative to DFS). |
| Most Stones Removed | Medium | Group stones by shared row or column. |
Avoid these
In the interview
Recognising the pattern is half the score; saying the right things out loud is the other half. These are the sentences that earn the signal.
Reach for union-find when the problem is connectivity under a stream of merges and explain that, unlike re-running DFS, it answers connectivity incrementally as edges arrive.
Mention both optimisations by name, path compression and union by rank or size, and note they bring find and union to near-constant amortised time; leaving them out is a common quiet bug.
For cycle detection in an undirected graph, state the rule that an edge whose endpoints already share a root would create a cycle, which doubles as the redundant-edge answer.
disjoint set union - dsu pattern - connected components union find
An external resource we recommend. AlgoExpert is not affiliated with us and we earn nothing from this link.
Keep going
Track a contiguous subarray or substring without re-scanning it from scratch.
Walk two indices toward or alongside each other to avoid a nested loop.
Halve the search space each step over any monotonic condition, not just sorted arrays.
Solve overlapping subproblems once, store the results, and build the answer up.
See all coding patterns, the coding questions for your role, and the behavioral round.