Union-Find (Disjoint Set Union) for Coding Interviews: A Clear Guide

Union-Find, also called Disjoint Set Union or DSU, is a small data structure with an outsized role in coding interviews. It answers one question extremely fast: are these two elements in the same group? That makes it the natural tool for "number of connected components", "redundant connection", "accounts merge", "number of provinces", "graph valid tree", and Kruskal's minimum spanning tree. Many candidates know BFS and DFS well but freeze on Union-Find, so learning it is an easy way to stand out. The idea Each element starts in its own set. Every set has a representative, called the root. Two operations do all the work: - find(x): return the root of x's set. - union(a, b): merge the sets containing a and b. Two elements are connected when find(a) == find(b). A clean implementation parent = list(range(n)) rank = [0] * n def find(x): while parent[x] != x: parent[x] = parent[parent[x]] x = parent[x] return x def union(a, b): ra, rb = find(a), find(b) if ra == rb: return False if rank[ra] < rank[rb]: ra, rb = rb, ra parent[rb] = ra if rank[ra] == rank[rb]: rank[ra] += 1 return True Two optimizations matter Path compression makes each node on the find path point closer to the root, so future finds are faster. The version above uses path halving, a simple iterative form. Union by rank (or by size) attaches the shorter tree under the taller one so trees stay shallow. Together they make operations run in nearly constant amortized time, formally O(alpha(n)), where alpha is the inverse Ackermann function and is at most about 4 for any realistic input. In an interview, saying "effectively constant time" and naming both optimizations is enough. Pattern 1: Counting components Start with count = n. For every edge, if union returns True, decrement count. At the end, count is the number of connected components. This solves "number of provinces" and "number of connected components in an undirected graph" in a few lines. Pattern 2: Detecting cycles In an undirected graph, if union(a, b) returns False, a and b were already connected, so the edge creates a cycle. "Redundant connection" asks you to return exactly that edge. "Graph valid tree" checks that there are no cycles and exactly n - 1 edges. Pattern 3: Grouping by shared attributes "Accounts merge" groups accounts that share an email. Map each email to an index, union all emails within the same account, then collect emails by root and sort them. The trick is choosing what the elements are: here they are emails, not accounts. Pattern 4: Kruskal's minimum spanning tree Sort edges by weight, then add each edge if union returns True. Stop after n - 1 edges. This shows up in problems like "min cost to connect all points". Pattern 5: Grids and dynamic connectivity "Number of islands II" adds land cells one at a time and asks for the island count after each addition. BFS would recompute everything; Union-Find handles each addition by unioning with neighboring land cells, which is far faster. Map a cell to an index with row * cols + col. When BFS or DFS is better If you only need connectivity once on a static graph, DFS is just as good and may be simpler. Union-Find shines when edges arrive incrementally, when you need many connectivity queries, or when the problem is naturally about merging groups. Saying this trade-off out loud shows judgment. Common bugs - Comparing parent[a] == parent[b] instead of find(a) == find(b). - Forgetting to update the component count. - Mixing up indices when mapping strings or grid cells. - Recursive find causing stack overflow on large inputs without compression. Practice list Number of provinces, redundant connection, graph valid tree, accounts merge, number of islands II, satisfiability of equality equations, and min cost to connect all points. During live rounds, some candidates use Linkjob AI (https://linkjob.ai), which gives real-time help during job interviews and technical interviews, to keep their approach organized. With a twenty-line template memorized, Union-Find becomes one of the most dependable tools you have.