Coding interview pattern
Union-Find (Disjoint Set)
Track connectivity between elements with near-constant-time union and find.
The idea
How the union-find (disjoint set) pattern works
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
When to reach for it
- The problem is about connectivity, grouping, or merging sets incrementally.
- You need to detect cycles in an undirected graph as edges are added.
- You count or track connected components under a stream of unions.
- You are implementing Kruskal's MST.
Cost
Time & space complexity
| 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
Walkthrough: Number of connected components in a graph
- 1Initialise each node as its own parent (every node is its own component).
- 2Start a component count equal to the number of nodes.
- 3For each edge, find the roots of both endpoints; if they differ, union them and decrement the count.
- 4If the roots are already equal, the edge is redundant (and would form a cycle).
- 5After processing all edges, the count is the number of connected components.
Translatable skeleton
The shape in pseudocode
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
Curated problem set
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
Common pitfalls
- Skipping path compression or union by rank, degrading to near-linear find.
- Forgetting to find the root before comparing or unioning.
- Off-by-one when mapping 2D grid cells to 1D parent indices.
- Decrementing the component count when the roots were already equal.
In the interview
How to communicate it live
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.
Also searched as
disjoint set union - dsu pattern - connected components union find
Last reviewed by the site editor: June 2026
An external resource we recommend. AlgoExpert is not affiliated with us and we earn nothing from this link.
Sources
- 1.5 Case Study: Union-Find Sedgewick and Wayne, Princeton University
- 4.3 Minimum Spanning Trees (Kruskal's algorithm) Sedgewick and Wayne, Princeton University
- Disjoint-set data structure Wikipedia
Next up
Patterns that pair well with this one
Real problems rarely match a single pattern. Interviewers like to combine this one with these.
- Sliding Window
Track a contiguous subarray or substring without re-scanning it from scratch.
- Two Pointers
Walk two indices toward or alongside each other to avoid a nested loop.
- Binary Search
Halve the search space each step over any monotonic condition, not just sorted arrays.
- Dynamic Programming
Solve overlapping subproblems once, store the results, and build the answer up.
Round out your prep
See all coding patterns, the coding questions for your role, and the behavioral round.