Pattern 22 of 27

Union Find

Track which elements share a group with near-constant-time merges and lookups, ideal when connections arrive one at a time.

Cost: Near O(1) amortised per operation, O(n) space
Problems: 6

When to reach for it

The prompt asks about connected groups, or whether two items are connected.
Edges or equalities are added over time.
You need to know the moment an added edge closes a cycle.

How it works

Union find stores a parent pointer for every element, and following parents leads to a root that names the group. Union links one root under the other, and find shortens the path it walks so later lookups are nearly immediate. With path compression plus union by size, a long sequence of operations costs close to O(1) each. It answers connectivity questions incrementally, which a fresh BFS after every new edge cannot do cheaply.

The template

Written for Redundant Connection (write-up)

def find_redundant_connection(edges):
    parent = list(range(len(edges) + 1))

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

    for a, b in edges:
        ra, rb = find(a), find(b)
        if ra == rb:
            return [a, b]             # already connected: this edge closes a cycle
        parent[ra] = rb
    return []

Open in the editor Trace it line by line

Six problems, in learning order

1.Number of ProvincesLeetCode 547Union every connected pair and count the remaining roots.Medium
2.Redundant ConnectionLeetCode 684The first edge whose endpoints already share a root.Medium
3.Number of Operations to Make Network ConnectedLeetCode 1319At least n - 1 cables are needed; the answer is the component count minus one.Not in the curated 370 yet.Medium
4.Remove Max Number of Edges to Keep Graph Fully TraversableLeetCode 1579Two union-find copies, adding the edges both people can use first.Not in the curated 370 yet.Hard
5.Satisfiability of Equality EquationsLeetCode 990Union every equality, then check that no inequality joins one group.Not in the curated 370 yet.Medium
6.Smallest String With SwapsLeetCode 1202Characters inside one component can be sorted freely across their indices.Not in the curated 370 yet.Medium

What usually goes wrong

Comparing the elements themselves instead of their roots.
Skipping path compression, which lets parent chains grow long.
Decreasing the component count on every union, including unions of elements already in one group.

Union Find, answered

When should I use the union find pattern?

The prompt asks about connected groups, or whether two items are connected. Edges or equalities are added over time. You need to know the moment an added edge closes a cycle.

What is the time complexity of union find?

Near O(1) amortised per operation, O(n) space. It answers connectivity questions incrementally, which a fresh BFS after every new edge cannot do cheaply.

Which problem should I start with for union find?

Start with Number of Provinces (LeetCode 547, Medium). Union every connected pair and count the remaining roots. The six problems on this page are in learning order.