What is Union-Find (Disjoint Set Union)?
Learn what Union-Find (DSU) is, how path compression and union by rank work, and how to answer this data structures interview question.
Expected Interview Answer
Union-Find, or Disjoint Set Union (DSU), is a data structure that tracks a collection of non-overlapping sets and answers "are these two elements in the same group" and "merge these two groups" in near-constant time using path compression and union by rank.
Each element starts as its own set with itself as parent. The find operation walks parent pointers to the root representative of a set, and path compression flattens the chain by pointing every visited node directly at the root during the walk. The union operation merges two sets by attaching one root under the other, and union by rank or size keeps the resulting tree shallow by always attaching the smaller tree under the larger one's root. Combined, these two optimizations give an amortized time complexity so close to O(1) per operation that it is described as O(alpha(n)), the inverse Ackermann function, which is effectively constant for any realistic input size. This makes Union-Find the standard tool for Kruskal's minimum spanning tree algorithm, cycle detection in undirected graphs, and dynamic connectivity queries.
- Near O(1) amortized find and union
- Simple array-based implementation
- Core of Kruskal MST and cycle detection
- Efficient dynamic connectivity tracking
AI Mentor Explanation
Union-Find is like merging local cricket clubs into regional associations: each player starts in their own tiny club, and when two clubs agree to merge, one club's captain becomes the representative for both under the bigger association. Checking whether two players belong to the same association means following each player up through captains until you reach the top representative, and comparing those two representatives. Every time you do that lookup, you also update each player's record to point straight at the top association instead of the intermediate captain, so future lookups are instant. This flattening is why after enough merges and lookups, finding anyone's top association becomes almost immediate.
Step-by-Step Explanation
Step 1
Initialize
Every element starts as its own parent, forming n singleton sets.
Step 2
Find with path compression
Walk up parent pointers to the root, then re-point every visited node directly to that root.
Step 3
Union by rank or size
Attach the root of the smaller tree under the root of the larger tree to keep trees shallow.
Step 4
Query connectivity
Two elements are in the same set if find(a) equals find(b), used for cycle detection and Kruskal MST.
What Interviewer Expects
- Explain both path compression and union by rank/size as required optimizations
- State the near-constant amortized time complexity O(alpha(n))
- Give a real use case: Kruskal MST, cycle detection, dynamic connectivity
- Distinguish Union-Find from a graph traversal approach for connectivity
Common Mistakes
- Implementing find without path compression, degrading to O(n) chains
- Unioning arbitrarily without rank/size, creating long skewed trees
- Confusing Union-Find with a general graph adjacency structure
- Forgetting that Union-Find cannot easily support splitting sets apart
Best Answer (HR Friendly)
“Union-Find is a structure I use whenever I need to quickly answer whether two items belong to the same group and merge groups together. It keeps a representative for each group and uses two tricks, path compression and union by rank, so that after enough operations checking group membership becomes almost instant.”
Code Example
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # path compression
return self.parent[x]
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False
if self.rank[ra] < self.rank[rb]:
ra, rb = rb, ra
self.parent[rb] = ra
if self.rank[ra] == self.rank[rb]:
self.rank[ra] += 1
return True
uf = UnionFind(5)
uf.union(0, 1)
uf.union(1, 2)
print(uf.find(0) == uf.find(2)) # TrueFollow-up Questions
- How would you use Union-Find to detect a cycle in an undirected graph?
- How does Union-Find power Kruskal’s minimum spanning tree algorithm?
- Why is the amortized complexity O(alpha(n)) considered effectively constant?
- How would you track the size of each set alongside Union-Find?
MCQ Practice
1. What is the amortized time complexity of find and union with both path compression and union by rank?
With both optimizations combined, the amortized cost per operation is O(alpha(n)), the inverse Ackermann function.
2. What does path compression do during a find operation?
Path compression flattens the tree by making every node on the find path point directly at the root.
3. Which classic algorithm relies on Union-Find to avoid cycles while building a spanning tree?
Kruskal’s algorithm uses Union-Find to check whether adding an edge would create a cycle.
Flash Cards
What two optimizations make Union-Find near-constant time? — Path compression and union by rank (or size).
What does find(x) return? — The root representative of the set containing x.
Name a classic algorithm that uses Union-Find. — Kruskal’s minimum spanning tree algorithm.
What is the amortized complexity per operation? — O(alpha(n)), the inverse Ackermann function, effectively O(1).