linkjobai

Union-Find in Coding Interviews: The Disjoint Set Pattern Explained Simply

Union-Find (also called a disjoint set union, or DSU) shows up in interviews more often than people expect: counting connected components, detecting a cycle in an undirected graph, redundant connection, number of provinces, and grouping equivalent strings. Once you can write it from memory in two minutes, a whole family of graph questions becomes easy.

The idea

Every element starts in its own set. Each set is a tree, and the root of the tree is the set's representative. Two operations matter:

  • find(x) walks up to the root of x's tree.
  • union(a, b) finds both roots and, if they differ, attaches one root under the other.

The interview-ready version

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.count = n  # number of components

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # path halving
            x = self.parent[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False  # already connected: this edge closes a cycle
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.count -= 1
        return True

With path compression (here, path halving) and union by size, each operation runs in near-constant amortized time, formally O(α(n)), the inverse Ackermann function. Say that out loud; interviewers like hearing that you know why it is fast.

Three questions it solves directly

  1. Number of connected components: union every edge, then return count.
  2. Redundant connection: process edges in order; the first edge where union returns False is the answer.
  3. Accounts merge / equivalent groups: map each item to an index, union items that appear together, then bucket by find.

When to prefer BFS/DFS instead

If the graph is given once and you only need components, DFS is just as good. Union-Find wins when edges arrive one at a time (dynamic connectivity) or when you need to answer "are these two connected?" many times.

Common mistakes

  • Comparing parent[a] == parent[b] instead of find(a) == find(b).
  • Forgetting to decrement the component count only on a successful union.
  • Using recursion for find in Python on huge inputs and hitting the recursion limit.

Practice tip

Write the class above five times on paper this week, then solve one connectivity problem a day using it. For live practice where you explain your reasoning out loud, I build Linkjob AI copilot, an assistant for technical interviews (disclosure: I work on it).