← Create New Paste

Union-Find (Disjoint Set Union) in Coding Interviews: Path Compression, Union by Rank and When to Re

6 views
Union-Find, also called Disjoint Set Union (DSU), is one of those data structures that rarely appears in a textbook chapter on its own but shows up again and again in coding interviews: number of connected components, redundant connection, accounts merge, number of provinces, satisfiability of equality equations, and Kruskal's minimum spanning tree. Once you can write it from memory in about two minutes, a whole family of graph problems becomes routine. 1. What problem it solves You have n elements and a stream of "these two belong together" statements. You need to answer "are a and b in the same group?" quickly, and possibly "how many groups are there now?". BFS or DFS can answer this for a static graph, but when edges arrive one at a time, or when you need to detect the first edge that creates a cycle, Union-Find is the cleaner tool. 2. The core idea Every element points to a parent. The root of each tree is the representative of its group. find(x) follows parent pointers up to the root. union(a, b) finds both roots and, if they differ, attaches one root under the other. 3. The two optimisations interviewers expect Path compression: during find, point every node you visit directly to the root. The next lookup for any of them is one hop. Union by rank (or by size): always attach the shorter or smaller tree under the taller or larger one, so trees stay shallow. With both, each operation runs in amortised O(alpha(n)) time, where alpha is the inverse Ackermann function. In an interview you can say "effectively constant time" and mention the inverse Ackermann bound if asked. 4. A template you can write quickly parent = list(range(n)); rank = [0] * n; components = n find(x): while parent[x] != x: parent[x] = parent[parent[x]]; x = parent[x]; return x union(a, b): ra, rb = find(a), find(b); if ra == rb return False; if rank[ra] < rank[rb] swap; parent[rb] = ra; if rank[ra] == rank[rb] rank[ra] += 1; components -= 1; return True The one-line "parent[x] = parent[parent[x]]" is path halving, an iterative version of path compression that avoids recursion depth problems in Python. 5. Patterns to recognise Cycle detection in an undirected graph: the first union that returns False is the redundant edge. Counting components: start with n and decrement on every successful union. Grouping by shared attributes: in Accounts Merge, union each email with the first email of its account, then group by root. Equality constraints: process all "a == b" first with union, then check every "a != b" for a contradiction. Kruskal's MST: sort edges by weight and add each edge whose union succeeds. Grid problems: map cell (r, c) to r * cols + c and union with neighbours, which is handy for "number of islands II" where land is added over time. 6. Common mistakes Comparing parent[a] == parent[b] instead of find(a) == find(b). Forgetting to union roots rather than the original nodes. Using recursion for find on 10^5 nodes in Python and hitting the recursion limit. Not mapping string keys (emails, variable names) to integer ids, or using a dictionary-based parent map without initialising new keys. 7. How to talk about it in the interview Say why you chose it: "edges arrive incrementally and I only need connectivity, not paths, so Union-Find fits better than re-running DFS." State the complexity with both optimisations. If the interviewer asks for paths or shortest distances, explain that Union-Find cannot give those and switch to BFS or Dijkstra. 8. Practice list Number of Provinces, Redundant Connection, Accounts Merge, Satisfiability of Equality Equations, Most Stones Removed with Same Row or Column, Min Cost to Connect All Points (Kruskal), Number of Islands II. When you are in a live coding round, the pressure is less about remembering the template and more about explaining your reasoning clearly while you type. Tools such as Linkjob AI (https://linkjob.ai) give real-time help during job interviews and technical interviews, which can keep you on track when a follow-up question about complexity or edge cases arrives mid-solution.
Created Nov 15, 2026 15:28 Expires Nov 15, 2027 15:28