Union-Find in Coding Interviews: Path Compression, Union by Rank, and When to Reach for It

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.

The core idea

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.

Optimization 1: path compression

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.

Optimization 2: union by rank (or size)

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.

A clean template (Python)

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.

How to recognize a union-find problem

When not to use it

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.

Common mistakes under time pressure

  1. Comparing parent[a] == parent[b] instead of find(a) == find(b). Parents are not roots until compressed.
  2. Forgetting to map 2D grid cells to ids: use r * cols + c.
  3. Recursive find on 105+ nodes in Python can hit the recursion limit before compression kicks in, so prefer the iterative version above.
  4. Not stating complexity: say "O(α(n)) amortized per operation, O(n) space."

A quick practice plan

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.

Hosted on ShareYourHTML.com  ·  Report abuse