Union-Find Explained for Coding Interviews (2026)

Union-find (also called disjoint set union, or DSU) is the data structure to reach for when a problem asks whether two things are connected, how many groups exist, or whether adding an edge creates a cycle. It supports two operations, find (which group does x belong to) and union (merge two groups), both running in effectively constant time once you add the two standard optimizations. If you can recognize the "grouping and connectivity" signal, a whole class of graph problems collapses into 20 lines of code.

This guide covers the template you should memorize, the amortized complexity and why it holds, the four problem patterns that account for most union-find interview questions, and the traps that cost people points. We run mock interviews all day, and the pattern we see most is candidates reaching for DFS or BFS on problems where union-find is shorter, faster to write, and far less bug-prone.

The template you should memorize

Two optimizations make union-find fast: union by rank/size (attach the smaller tree under the larger one) and path compression (flatten the tree during find). Skip them and you get O(n) per operation. Include both and you get near-constant time.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))   # each node is its own root
        self.rank = [0] * n            # tree height upper bound
        self.count = n                 # number of disjoint sets

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # path compression
            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 is redundant
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        self.count -= 1
        return True

Two details worth calling out. The count field gives you the number of connected components for free, which answers a surprising number of questions directly. And union returning False tells you the two nodes were already in the same set, which is exactly how you detect a redundant edge or a cycle.

Complexity, stated precisely

Building the parent and rank arrays is O(n). After that, with both union by rank and path compression, a sequence of m operations runs in O(m · α(n)) total, where α is the inverse Ackermann function. With appropriate path compaction and linking heuristics, the problem can be solved in O(m · α(n, m/n)) time complexity, where n is the number of elements, m is the number of operations, and α is a functional inverse of Ackermann's function.

The key nuance for interviews: α(n) is not the cost of a single operation, it is the amortized cost averaged across the whole sequence. For any n you will ever see in an interview, α(n) is at most 4, so people describe it as "effectively constant." Say "amortized near-constant, O(m·α(n)) across m operations" and you sound precise rather than hand-wavy.

If you use only union by rank/size without path compression, DSU with union by size / rank, but without path compression works in O(log n) per operation, which is still fine for most inputs but worth knowing as a fallback.

Pattern 1: counting connected components

When a problem gives you nodes and edges and asks "how many groups," initialize a DSU, union every edge, and read count. The classic is Number of Provinces (LeetCode 547), where an isConnected matrix defines friendships and you count friend circles.

Here is the full flow on a tiny edge list, which is worth being able to trace out loud:

nodes: 0,1,2,3,4   edges: (0,1), (1,2), (3,4)
start:  parent = [0,1,2,3,4]   count = 5
union(0,1): merge -> count = 4
union(1,2): find(1)=0, find(2)=2, merge -> count = 3
union(3,4): merge -> count = 2
answer: 2 components  {0,1,2} and {3,4}

Pattern 2: cycle and redundant-edge detection

For an undirected graph, if you call union(a, b) and both endpoints already share a root, that edge closes a cycle. This is the entire idea behind Redundant Connection (LeetCode 684): process edges in order and return the first one whose union returns False.

One trap that costs people the problem: this cycle-detection trick applies to undirected graphs only. Directed-graph cycle detection needs DFS with a recursion stack or Kahn's topological sort, not union-find. If the edges have direction and the cycle must respect that direction, DSU will give wrong answers because it ignores orientation entirely. When you are unsure which tool fits, our guide on topological sort interview questions pairs naturally with this one, since the two techniques divide the graph-cycle world between them.

Pattern 3: grouping by a shared property

Sometimes the "edges" are implicit: two items belong together if they share an attribute. Accounts Merge (LeetCode 721) is the canonical example, where accounts merge if they share any email address. The move is to union every element that shares the property, then collect members by root.

This pattern often involves non-integer elements (emails, strings, coordinates). Union-find works on integer indices, so map each distinct element to an index first, usually with a hash map:

index = {}
def get_id(key):
    if key not in index:
        index[key] = len(index)
    return index[key]

The cost of this mapping is O(k) extra space, where k is the number of distinct elements, and each lookup or insertion is O(1) amortized assuming a hash map. Build the index, size your DSU to len(index), then union normally.

Pattern 4: Kruskal's MST and edge classification

Union-find is the engine inside Kruskal's minimum spanning tree algorithm. Just as in the simple version of the Kruskal algorithm, we sort all the edges of the graph in non-decreasing order of weights, put each vertex in its own set, iterate through all edges in sorted order and for each edge determine whether the ends belong to different trees, then perform the union. Sorting dominates, so the whole thing runs in O(M log N).

The hardest interview variant in this family is Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree (LeetCode 1489), a problem we tag as staff-level in the DevInterview question bank. You compute the MST weight, then for each edge test whether forcing it out raises the weight (critical) or forcing it in still achieves the MST weight (pseudo-critical). It appears in senior-level and staff-level interview sets at large tech firms, and it is a good stress test because you run Kruskal many times and need a DSU that resets cleanly. If you are targeting those loops, our company interview breakdowns show which firms lean graph-heavy.

Quick reference

Problem	Signal	DSU time
Number of Provinces (LC 547)	count groups	O(n² · α(n))
Redundant Connection (LC 684)	first cycle-closing edge	O(n · α(n))
Accounts Merge (LC 721)	group by shared email	O(k · α(k) + sort)
Graph Valid Tree (LC 261)	connected and acyclic	O((n+e) · α(n))
Critical/Pseudo-Critical MST Edges (LC 1489)	Kruskal, run repeatedly	O(E² · α(V))

Our editorial take: a large fraction of union-find interview questions reduce to one of these four patterns. Learn the template cold, practice explaining the amortized complexity, and drill recognizing the "connectivity or grouping" signal, and you will handle most of what shows up.

FAQ

When should I use union-find instead of DFS or BFS?

Use union-find when the graph is static or edges only get added, and the question is about connectivity, group count, or cycle detection. If you need shortest paths, traversal order, or the graph loses edges over time, DFS/BFS or other tools fit better. For a valid-tree check like LeetCode 261, DSU is usually the cleaner solution.

Do I really need both optimizations?

For interviews, yes. Path compression plus union by rank/size gives you the near-constant amortized bound and shows the interviewer you know the data structure properly. Union by rank alone still gives O(log n) per operation, so it is an acceptable fallback if you blank on compression, but write both when you can.

Can union-find detect cycles in a directed graph?

No. The cycle-detection trick works only for undirected graphs because DSU ignores edge direction. For directed graphs use DFS with a recursion stack or Kahn's algorithm for topological sorting.

How do I use union-find on strings or coordinates?

Map each distinct element to an integer index with a hash map, size the DSU to the number of distinct elements, then union as usual. This adds O(k) space for k distinct elements and O(1) amortized per lookup, which is exactly the approach for Accounts Merge.