Union-Find Pattern: Template + 83 LeetCode Problems

What the union-find pattern is

Union-Find — a disjoint set union, or DSU — maintains a partition of elements into groups under two operations: merge two groups, and ask which group an element belongs to. Each group is a tree whose root is its name, so the question "are these connected?" reduces to "do they have the same root?". Two optimisations make it fast enough to disappear from the complexity analysis. Path compression flattens the tree on the way back from a lookup, pointing every node visited straight at the root. Union by size or rank always hangs the smaller tree under the larger one, so no chain gets long in the first place. Together they give an amortised inverse-Ackermann cost per operation, effectively constant. Reach for it instead of a graph traversal when edges arrive one at a time and the question is about connectivity as they arrive — that is the case a DFS cannot answer without re-running.

When to use it

• —Edges or merges arrive incrementally and you must answer connectivity questions between them.
• —You need the number of connected components, or the size of the component containing a node.
• —The problem asks whether adding an edge creates a cycle — union returning false is exactly that.
• —You are building a minimum spanning tree with Kruskal's algorithm.
• —Grouping is transitive: accounts that share an email, equations that chain equalities, stones in the same row or column.

The union-find template in Python

The shape, not a solution to any one problem. Adapt the condition and the summary being maintained; the skeleton stays the same across the 83 problems listed below.

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

    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):
        root_a, root_b = self.find(a), self.find(b)
        if root_a == root_b:
            return False                     # already together: this edge is a cycle
        if self.size[root_a] < self.size[root_b]:
            root_a, root_b = root_b, root_a  # hang the smaller tree under the larger
        self.parent[root_b] = root_a
        self.size[root_a] += self.size[root_b]
        return True

Complexity characteristics

Time

O(α(n)) amortised per operation

Auxiliary space

O(n)

With path compression and union by size applied together, m operations over n elements cost O(m·α(n)), where α is the inverse Ackermann function and is at most 4 for any n that fits in memory — effectively constant, which is why union-find usually disappears from the complexity of the algorithm using it. Either optimisation on its own is materially worse: union by size alone leaves O(log n) per operation. The space is the parent and size arrays.

All 83 union-find LeetCode problems

Every problem in the library the union-find pattern applies to, grouped by LeetCode's own difficulty rating. 66 of the 83 carry a complete Python solution with a worked example and complexity analysis; the rest are listed for completeness, with the LeetCode Premium ones marked.

Related patterns

Problems sit in more than one pattern more often than not, and the overlap is where the interesting follow-up questions live.

Union-Find pattern FAQ

More ways in: all 22 patterns, the curated study lists, or the full problem list.