Union-Find
Track a collection of elements partitioned into non-overlapping sets with just two operations — find and union. With path compression and union by rank, both run in near-constant amortized time.
A forest of trees, stored in one array
Union-Find (a.k.a. Disjoint Set Union) answers two questions about a collection of elements:
- Find — which set does element x belong to? Returns the set's root (representative).
- Union — merge the sets containing x and y.
Each set is a tree; each element stores only its parent, so the whole structure
is a single array: parent[i]. Roots point to themselves.
union(x, y) returning False means x and y were already connected —
adding this edge would create a cycle. Half of all Union-Find problems are solved by
just watching for that False.
Two tricks that make it near-O(1)
Opt 1Path compression
During find(x), make every node on the path point directly to the root.
The first find pays for the walk; every later find on those nodes is O(1).
Opt 2Union by rank
Always attach the shorter tree under the root of the taller tree, so tree height only grows when two equal-rank trees merge.
| Without optimizations | Path compression only | Both optimizations |
|---|---|---|
| O(n) per op | O(log n) amortized | O(α(n)) ≈ O(1) amortized |
α(n) is the inverse Ackermann function — ≤ 4 for any input that fits in the universe, so treat it as constant.
When to reach for it
Union-Find vs. DFS/BFS
| Union-Find | DFS / BFS | |
|---|---|---|
| Graph type | Edges arrive incrementally | Static / fully known |
| Query type | “Same component?” | “What's the path?” |
| Repeated queries | Excellent — amortized O(1) | Must re-traverse each time |
| Cycle detection | Undirected graphs | Both directed and undirected |
| Implementation | One array, very compact | Adjacency list + stack/queue |
A five-question checklist before you commit:
- Is this about grouping / connectivity? → consider Union-Find.
- Are edges added dynamically? → Union-Find beats rebuilding adjacency lists.
- Need a component count? → track
countinside union. - Detecting cycles in an undirected graph? → union returns False when both endpoints already share a root.
- Need the actual path between nodes? → use BFS/DFS instead; Union-Find only knows connectivity.
The complete class to memorize
Roughly 20 lines, and it drops into every problem in this pattern unchanged.
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.count = n # number of connected components
def find(self, x):
# Path compression: point every node to root
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
rx, ry = self.find(x), self.find(y)
if rx == ry:
return False # already in same set (cycle!)
# Union by rank
if self.rank[rx] < self.rank[ry]:
rx, ry = ry, rx
self.parent[ry] = rx
if self.rank[rx] == self.rank[ry]:
self.rank[rx] += 1
self.count -= 1
return True
def connected(self, x, y):
return self.find(x) == self.find(y)rx is always
the higher-rank root, and only bumps rank on a tie. count decrements only when
a merge actually happens.
Seven shapes the interview takes
P1Count connected components — LC 323
Union every edge; the answer falls out of the count field.
def countComponents(n, edges):
uf = UnionFind(n)
for u, v in edges:
uf.union(u, v)
return uf.countP2Redundant connection (cycle edge) — LC 684
The graph is a tree plus one extra edge. The first union that returns False is the edge that closed a cycle.
def findRedundantConnection(edges):
uf = UnionFind(len(edges) + 1)
for u, v in edges:
if not uf.union(u, v):
return [u, v] # this edge connects already-connected nodesP3Graph valid tree — LC 261
A valid tree has exactly n - 1 edges and no cycles (which also forces connectivity).
def validTree(n, edges):
if len(edges) != n - 1:
return False
uf = UnionFind(n)
for u, v in edges:
if not uf.union(u, v):
return False # cycle detected
return TrueP4Accounts merge (equivalence grouping) — LC 721
A shared email means two accounts are the same person — a classic equivalence relation. Union account indices via shared emails, then group by root.
def accountsMerge(accounts):
from collections import defaultdict
email_to_id = {} # email -> first account index that owns it
email_to_name = {} # email -> account name
uf = UnionFind(len(accounts))
for i, account in enumerate(accounts):
name = account[0]
for email in account[1:]:
email_to_name[email] = name
if email in email_to_id:
uf.union(i, email_to_id[email])
else:
email_to_id[email] = i
# Group emails by root account
groups = defaultdict(set)
for email, idx in email_to_id.items():
root = uf.find(idx)
groups[root].add(email)
return [[email_to_name[next(iter(emails))]] + sorted(emails)
for emails in groups.values()]P5Number of islands, Union-Find style — LC 200
Flatten the grid: cell (r, c) becomes index r * cols + c. Union each land
cell with its right and down neighbors, then subtract the water cells from the count.
def numIslands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
uf = UnionFind(rows * cols)
water = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == '0':
water += 1
continue
# Union with right and down neighbors
for dr, dc in [(0, 1), (1, 0)]:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
uf.union(r * cols + c, nr * cols + nc)
return uf.count - waterDFS flood-fill is simpler for the static version — Union-Find wins on the follow-up where land is added dynamically (LC 305).
P6Longest consecutive sequence — LC 128
Union each number's index with the index of num + 1, tracking component sizes manually.
def longestConsecutive(nums):
if not nums:
return 0
num_set = set(nums)
val_to_idx = {v: i for i, v in enumerate(nums)}
uf = UnionFind(len(nums))
size = [1] * len(nums)
for num in nums:
if num + 1 in val_to_idx:
rx = uf.find(val_to_idx[num])
ry = uf.find(val_to_idx[num + 1])
if rx != ry:
# Track sizes manually
new_size = size[rx] + size[ry]
uf.union(val_to_idx[num], val_to_idx[num + 1])
root = uf.find(val_to_idx[num])
size[root] = new_size
return max(size) if size else 0The hash-set approach (check "am I the start of a run?") is O(n) and simpler for this specific problem — Union-Find shown for the technique.
P7Equality equations (two-pass) — LC 990
Process every a==b first to build the groups, then check every
a!=b against them. Order matters — that's the whole trick.
def equationsPossible(equations):
uf = UnionFind(26) # 26 lowercase letters
# First pass: process all '==' equations
for eq in equations:
if eq[1] == '=':
uf.union(ord(eq[0]) - ord('a'), ord(eq[3]) - ord('a'))
# Second pass: check all '!=' equations
for eq in equations:
if eq[1] == '!':
if uf.connected(ord(eq[0]) - ord('a'), ord(eq[3]) - ord('a')):
return False
return TrueComplexity reference
| Problem | Time | Space |
|---|---|---|
| Connected Components (323) | O(n · α(n)) | O(n) |
| Redundant Connection (684) | O(n · α(n)) | O(n) |
| Graph Valid Tree (261) | O(n · α(n)) | O(n) |
| Accounts Merge (721) | O(nk · α(nk)) | O(nk) |
| Number of Islands (200) | O(RC · α(RC)) | O(RC) |
| Longest Consecutive (128) | O(n · α(n)) | O(n) |
| Equality Equations (990) | O(n · α(26)) | O(26) |
| Evaluate Division (399) | O(n · α(n)) | O(n) |
Weighted Union-Find
When relationships carry values — "a / b = 2.0" in LC 399 Evaluate Division —
store a weight on each parent pointer: weight[i] is the ratio from i
to parent[i]. Path compression multiplies weights down the chain.
class WeightedUnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.weight = [1.0] * n # weight[i] = ratio from i to parent[i]
def find(self, x):
if self.parent[x] != x:
root = self.find(self.parent[x])
self.weight[x] *= self.weight[self.parent[x]]
self.parent[x] = root
return self.parent[x]
def union(self, x, y, w):
# w = value[x] / value[y]
rx, ry = self.find(x), self.find(y)
if rx == ry:
return
self.parent[rx] = ry
self.weight[rx] = w * self.weight[y] / self.weight[x]
def query(self, x, y):
if self.find(x) != self.find(y):
return -1.0
return self.weight[x] / self.weight[y]Where union-find goes wrong
find() degrades to O(n) on a degenerate chain. It's one line
inside find — never leave it out.
UnionFind(n + 1)
(index 0 goes unused) or subtract 1 everywhere.
False means "already connected" — a potential cycle — not an error.
Flipping the meaning silently inverts your cycle detection.
Practice ladder
In this order — easiest first. Tick each one as you solve it, and re-solve anything that took more than 25 minutes two days later.