What is a Disjoint Set Union with Path Compression?
Learn how Union-Find with path compression and union by rank achieves near-constant-time set operations, with Python code.
Expected Interview Answer
A Disjoint Set Union (also called Union-Find) tracks a collection of non-overlapping sets, supporting find (which set does an element belong to) and union (merge two sets) operations, and path compression flattens the tree during find so future lookups become nearly O(1).
Each set is represented as a tree where every node points to a parent, and the set's identity is its root; find walks parent pointers up to the root. Path compression makes every node visited during a find point directly to the root afterward, so repeated finds on the same or nearby elements become dramatically faster. Combined with union by rank or size — always attaching the smaller tree under the bigger tree's root — the amortized time per operation drops to O(α(n)), the inverse Ackermann function, which is effectively constant for any realistic input size. This combination powers Kruskal's minimum spanning tree algorithm, cycle detection in undirected graphs, and dynamic connectivity queries like “are these two nodes in the same network right now.”
- Near-O(1) amortized time per operation with both optimizations combined
- Flattens tree depth automatically via path compression
- Backbone of Kruskal's MST algorithm and connectivity queries
- Simple array-based implementation with no complex balancing logic
AI Mentor Explanation
A tournament tracks which teams belong to the same regional pool by having each team point to a “pool captain” team, and finding a team's pool means following captain pointers up to the top captain. Every time you trace a team up to its top captain, you re-point that team directly to the top captain so the next lookup is instant instead of retracing the whole chain. When two pools merge, you attach the smaller pool's top captain under the bigger pool's top captain, keeping chains short. This flattening trick, combined with always attaching small under big, is exactly what makes Union-Find operations nearly constant time.
Step-by-Step Explanation
Step 1
Initialize each element as its own set
Every element starts as its own parent, forming n single-node trees.
Step 2
find(x) walks to the root
Follow parent pointers until reaching a node that is its own parent (the root).
Step 3
Apply path compression
After finding the root, re-point every visited node on the path directly to that root.
Step 4
union(x, y) by rank or size
Find both roots; attach the smaller tree's root under the larger tree's root to keep future finds shallow.
What Interviewer Expects
- Explain find and union operations clearly with the parent-pointer model
- Explain path compression and why it flattens the tree
- Mention union by rank/size as the complementary optimization
- State the near-O(1) amortized (inverse Ackermann) time complexity with both optimizations
Common Mistakes
- Implementing union without union by rank/size, allowing trees to degenerate into long chains
- Forgetting path compression, missing the main performance win
- Confusing Union-Find with a general tree or graph traversal structure
- Not recognizing O(α(n)) as effectively constant time for practical input sizes
Best Answer (HR Friendly)
“A Disjoint Set Union, or Union-Find, keeps track of groups of items and lets me quickly check if two items are in the same group or merge two groups together. Path compression is a trick where, every time I look up an item's group, I flatten the path so the next lookup is almost instant, which is why this structure stays fast even on huge datasets.”
Code Example
class DisjointSet:
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, x, y):
root_x, root_y = self.find(x), self.find(y)
if root_x == root_y:
return False # already connected -> would form a cycle
if self.rank[root_x] < self.rank[root_y]:
root_x, root_y = root_y, root_x
self.parent[root_y] = root_x
if self.rank[root_x] == self.rank[root_y]:
self.rank[root_x] += 1
return TrueFollow-up Questions
- How does Union-Find power Kruskal's minimum spanning tree algorithm?
- How would you use Union-Find to detect a cycle in an undirected graph?
- What is the difference between union by rank and union by size?
- What does the O(α(n)) amortized time complexity actually mean in practice?
MCQ Practice
1. What does path compression do during a find operation?
Path compression flattens the tree by making every node on the find path point straight to the root.
2. What is the amortized time complexity of Union-Find with both path compression and union by rank?
The combination gives O(α(n)) amortized time, where α is the inverse Ackermann function, essentially constant.
3. Which algorithm relies directly on Union-Find to avoid forming cycles?
Kruskal's algorithm adds edges in weight order and uses Union-Find's find to skip edges that would close a cycle.
Flash Cards
What two operations does a Disjoint Set Union support? — find (which set does an element belong to) and union (merge two sets).
What does path compression optimize? — It flattens the tree during find, making future lookups nearly O(1).
What complements path compression for optimal performance? — Union by rank or size, always attaching the smaller tree under the larger.
What is the combined amortized time complexity? — O(α(n)), the inverse Ackermann function, effectively constant time.