Pattern 19 of 22
Union-Find Pattern: Template + 83 LeetCode Problems
Merge groups and ask whether two things are connected, both in near-constant time.
- Easy
- 1
- Medium
- 44
- Hard
- 38
What the union-find pattern is
Union-Find — a disjoint set union, or DSU — maintains a partition of elements into groups under two operations: merge two groups, and ask which group an element belongs to. Each group is a tree whose root is its name, so the question "are these connected?" reduces to "do they have the same root?". Two optimisations make it fast enough to disappear from the complexity analysis. Path compression flattens the tree on the way back from a lookup, pointing every node visited straight at the root. Union by size or rank always hangs the smaller tree under the larger one, so no chain gets long in the first place. Together they give an amortised inverse-Ackermann cost per operation, effectively constant. Reach for it instead of a graph traversal when edges arrive one at a time and the question is about connectivity as they arrive — that is the case a DFS cannot answer without re-running.
When to use it
- Edges or merges arrive incrementally and you must answer connectivity questions between them.
- You need the number of connected components, or the size of the component containing a node.
- The problem asks whether adding an edge creates a cycle — union returning false is exactly that.
- You are building a minimum spanning tree with Kruskal's algorithm.
- Grouping is transitive: accounts that share an email, equations that chain equalities, stones in the same row or column.
The union-find template in Python
The shape, not a solution to any one problem. Adapt the condition and the summary being maintained; the skeleton stays the same across the 83 problems listed below.
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
def find(self, x):
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # path halving
x = self.parent[x]
return x
def union(self, a, b):
root_a, root_b = self.find(a), self.find(b)
if root_a == root_b:
return False # already together: this edge is a cycle
if self.size[root_a] < self.size[root_b]:
root_a, root_b = root_b, root_a # hang the smaller tree under the larger
self.parent[root_b] = root_a
self.size[root_a] += self.size[root_b]
return TrueComplexity characteristics
- Time
- O(α(n)) amortised per operation
- Auxiliary space
- O(n)
With path compression and union by size applied together, m operations over n elements cost O(m·α(n)), where α is the inverse Ackermann function and is at most 4 for any n that fits in memory — effectively constant, which is why union-find usually disappears from the complexity of the algorithm using it. Either optimisation on its own is materially worse: union by size alone leaves O(log n) per operation. The space is the parent and size arrays.
Eyes only
Meet the union-find problem you did not practise.
In the live round, Stealth Interview reads the problem off your screen, returns a working solution with a step-by-step explanation and its time and space complexity, and transcribes what the interviewer says. It's a desktop app for macOS and Windows, invisible to screen sharing.
All 83 union-find LeetCode problems
Every problem in the library the union-find pattern applies to, grouped by LeetCode's own difficulty rating. 66 of the 83 carry a complete Python solution with a worked example and complexity analysis; the rest are listed for completeness, with the LeetCode Premium ones marked.
Related LeetCode topics
Easy (1)
| No. | Problem | Topics |
|---|---|---|
| 1971 | Find if Path Exists in Graph |
Medium (44)
Hard (38)
Union-Find pattern FAQ
What is the union-find pattern?
Union-Find — a disjoint set union, or DSU — maintains a partition of elements into groups under two operations: merge two groups, and ask which group an element belongs to.
How many LeetCode problems use the union-find pattern?
This page lists 83 LeetCode problems that the union-find pattern applies to: 1 Easy, 44 Medium and 38 Hard. 66 of them carry a complete Python solution with complexity analysis.
What is the time complexity of the union-find pattern?
O(α(n)) amortised per operation time and O(n) space. With path compression and union by size applied together, m operations over n elements cost O(m·α(n)), where α is the inverse Ackermann function and is at most 4 for any n that fits in memory — effectively constant, which is why union-find usually disappears from the complexity of the algorithm using it. Either optimisation on its own is materially worse: union by size alone leaves O(log n) per operation. The space is the parent and size arrays.
When should I use the union-find pattern in an interview?
Edges or merges arrive incrementally and you must answer connectivity questions between them. You need the number of connected components, or the size of the component containing a node.
Which union-find problem should I start with?
LeetCode 1971. Find if Path Exists in Graph is the lowest-numbered Easy problem on this page, which makes it the usual starting point: the technique is visible without the problem's own complications getting in the way.
What patterns are related to union-find?
Depth-First Search, Breadth-First Search, Topological Sort, Sorting. Problems frequently sit in more than one of these, and the overlap is where the interesting follow-up questions come from.
More ways in: all 22 patterns, the curated study lists, or the full problem list.