Union-Find (also called disjoint set union, or DSU) is one of those data structures that rarely shows up in day-to-day product code but appears again and again in interview problems about connectivity. It answers one question very quickly: are these two elements in the same group? And it lets you merge groups as you go. If you can write it from memory in under three minutes, a whole family of "medium" and "hard" graph questions becomes routine.
Every element points to a parent. Following parents eventually reaches a root, and the root is the representative of the set. Two elements are connected exactly when they share a root. Merging two sets means pointing one root at the other.
Without any optimizations the parent chains can degrade into a long linked list, making find O(n). Two small tricks fix that.
While walking up to the root, re-point every visited node directly at the root. The next lookup for any of those nodes takes one step. This is a one-line change in the recursive version and a two-pass loop in the iterative version.
When merging, attach the shorter tree under the taller one. "Rank" is an upper bound on tree height; "size" (number of elements) works just as well and is often more useful, because many problems ask for the size of the largest component anyway.
With both optimizations, each operation runs in amortized O(α(n)) time, where α is the inverse Ackermann function. For any input you will ever see, α(n) ≤ 4, so in an interview it is fine to call it "effectively constant" as long as you mention the amortized part.
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
self.components = n
def find(self, x):
root = x
while self.parent[root] != root:
root = self.parent[root]
while self.parent[x] != root: # path compression
self.parent[x], x = root, self.parent[x]
return root
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False # already connected: useful for cycle detection
if self.size[ra] < self.size[rb]:
ra, rb = rb, ra # union by size
self.parent[rb] = ra
self.size[ra] += self.size[rb]
self.components -= 1
return True
Two details interviewers like to see: union returns whether a merge actually happened, and the class tracks the number of components so you never need a second pass to count them.
union returns True.Union-Find cannot split sets, so problems that delete edges need another approach (or a trick like processing deletions in reverse as additions). It also does not give you paths, only membership. If the question asks for the shortest route between two nodes, use BFS or Dijkstra instead.
parent[a] == parent[b] instead of find(a) == find(b). Parents are not roots until compressed.r * cols + c.find on 105+ nodes in Python can hit the recursion limit before compression kicks in, so prefer the iterative version above.Write the template from scratch three times on different days, then solve: number of connected components, redundant connection, accounts merge, and one Kruskal MST problem. After that, try a grid problem where land is added cell by cell. Explaining out loud why path compression is safe (it never changes which root a node belongs to) is a great way to show depth.
If you practise explaining solutions like this under realistic interview conditions, a tool such as Linkjob AI can help with mock coding rounds. Disclosure: I work on Linkjob AI. The template and advice above work no matter how you prepare.
Written November 2026.