Union-Find

On this page

The Idea
Build It
Know It
Break It
Use It

Quick reference

find(i) — with path compression + union by rank	O(α(n)) ≈ O(1)
union(i, j) — with path compression + union by rank	O(α(n)) ≈ O(1)
find(i) — no path compression	O(n) worst case
union(i, j) — no union by rank	O(n) worst case

The Idea

Picture a party where people keep getting introduced to each other. Every introduction between two people joins their two friend groups into one bigger group. At any point someone might ask: 'are Alice and Bob in the same friend group?' Answering that by re-tracing every introduction that ever happened would be slow and get slower as the party goes on. Union-find answers it almost instantly instead, by having every person keep a pointer to their group's current leader — check whether Alice's leader and Bob's leader are the same person, and you have your answer without retracing anything.

That's the whole structure: two operations, find (who's your group's leader?) and union (merge two groups into one). No traversal, no adjacency list, no visited set — none of the machinery from the last two topics. It answers a narrower question than a general graph does — only 'same group or not' and 'merge these groups' — but it answers that narrower question far faster than running DFS/BFS from scratch every time someone asks.

DFS and BFS answer 'is there a path from A to B' by actually walking the graph, every time. Union-find answers 'have A and B ever been merged' by maintaining group leaders as merges happen, so the answer is nearly instant no matter how large the graph has grown.

Build It

The array

structure UnionFind:
    parent: array where parent[i] = i's parent (initially, every node is its own parent — its own group of one)
    rank: array where rank[i] = a rough upper bound on the height of i's tree (initially 0 for everyone)

find — follow parent pointers to the root, with path compression

function find(i):
    if parent[i] != i:
        parent[i] = find(parent[i])    // path compression: point straight at the root
    return parent[i]

A root is a node that is its own parent — the group's leader. Without the reassignment on the recursive call, find still works, it just walks the same long chain again on every future call. With it, every node visited on the way up gets repointed directly at the root before the call returns, so the next find() on any of them is one step, not a chain-walk. This is the amortized idea from Big-O Notation made concrete: any single call can still walk a long chain, but it also flattens that chain for every call after it.

union — merge two roots, with union by rank

function union(i, j):
    rootI = find(i)
    rootJ = find(j)
    if rootI == rootJ:
        return                          // already in the same group — nothing to do
    if rank[rootI] < rank[rootJ]:
        parent[rootI] = rootJ           // attach the shorter tree under the taller one
    elif rank[rootI] > rank[rootJ]:
        parent[rootJ] = rootI
    else:
        parent[rootJ] = rootI           // equal rank — pick one, and it grows taller
        rank[rootI] += 1

Attaching the shorter tree under the taller one (instead of, say, always attaching j under i regardless of size) is what keeps trees from growing into long chains as more unions happen. rank only changes when two equal-rank trees merge, since that's the one case where the resulting tree is genuinely one level taller than either input.

Know It

With both path compression and union by rank in place, find and union are essentially O(1) — technically O(α(n)), where α is the inverse Ackermann function. That name sounds intimidating; what it means in practice is simple: α(n) grows so slowly that for any number of elements you could ever actually have — not just thousands, but numbers far beyond the count of atoms in the observable universe — α(n) stays 4 or smaller. Say it plainly: for any real input, this is a constant number of steps. Drop either optimization and that guarantee is gone.

Operation	Time	Space	Why
find(i) — with path compression + union by rank	O(α(n)) ≈ O(1)	O(1)	Amortized over many calls, the tree stays so flat that walking to the root is, for any practical n, a small constant number of steps.
union(i, j) — with path compression + union by rank	O(α(n)) ≈ O(1)	O(1)	Two find() calls plus one pointer reassignment — same near-constant bound as find, since that's the dominant cost.
find(i) — no path compression	O(n) worst case	O(1)	Every call re-walks the full chain from i to the root with nothing flattened afterward — repeated unions in the wrong order can leave that chain n nodes long.
union(i, j) — no union by rank	O(n) worst case	O(1)	Always attaching one specific side (say, j under i) regardless of tree size can chain n single-node trees onto one growing spine, one union at a time.

Break It

find without path compression

the recursive call's result is never written back to parent[i]

The structure still gives correct answers — the root it finds is still the right root. What's lost is speed: every call re-walks the same chain from scratch instead of shortening it for next time. Enough unions chained in the wrong order and the tree degrades toward the same skewed, linked-list-like shape a BST degrades into under sorted insertions — a straight line of n nodes, one parent pointer at a time, and find becomes O(n).

union without rank (or size)

union always attaches one side under the other regardless of which tree is bigger

Same failure, different cause. If union(i, j) always makes j's root a child of i's root no matter their sizes, then a sequence like union(1,2), union(1,3), union(1,4), ... keeps stacking single-node trees onto the same growing spine — the tree's height grows by one with every union instead of staying flat. find still returns correct roots; it just has to walk further and further to get there.

Skipping the 'already same group' check before unioning

union(i, j) is called on two nodes that already share a root

This is inefficiency, not a bug — worth telling apart from the two cases above. Re-running find on both, discovering rootI == rootJ, and doing nothing wastes a little work but produces the exact same structure as if the check caught it early. Contrast with skipping path compression or rank: those don't crash anything either, but they compound into real O(n) slowdowns as more operations run. This one is just a wasted comparison, once.

Forgetting to initialize every node as its own parent

parent[i] isn't set to i for some node before any find/union runs

find(i) assumes it can walk parent pointers starting from the premise that an untouched node is its own root — a group of one, by itself. Skip the initialization (leave parent[i] at some default like 0 or undefined) and find(i) either walks toward the wrong root entirely or crashes on an undefined lookup, depending on the language. Every node needs parent[i] = i set explicitly before the structure is used, even nodes that never end up in any union call.

Use It

Number of Provinces

union() every pair the input matrix marks as connected, then count distinct roots — the number of distinct find() results across every node.

Medium

Redundant Connection

Process edges in order, union() each pair — the first edge where find(i) == find(j) before unioning is the one creating a cycle, and the answer.

Medium

Number of Operations to Make Network Connected

union() every existing cable, then count the resulting distinct groups — connecting k separate groups into one always takes exactly k - 1 more cables.

Medium

Accounts Merge

union() two accounts whenever they share an email; group every email afterward by its find() root, then combine and sort each group.

Medium

Lexicographically Smallest Equivalent String

union() each equivalent character pair, but modify union() to always attach under whichever root is alphabetically smaller — the same rank idea, repurposed to track 'smallest' instead of 'tallest.'

Medium

Most Stones Removed with Same Row or Column

union() any two stones sharing a row or column; the answer is total stones minus the number of distinct groups, since every group can be reduced to one stone.

Medium

Satisfiability of Equality Equations

union() every '==' pair first, then check every '!=' pair — if a '!=' pair shares a find() root, the equations contradict each other.

Medium

Smallest String With Swaps

union() every index pair connected by a swap; group indices by find() root, sort the characters within each group, and place them back in ascending index order.

Medium

Evaluate Division

A weighted variant: union() tracks not just the parent but the ratio to it, so find() has to accumulate a product along the path to the root instead of just returning who the root is.

Medium

The Earliest Moment When Everyone Become Friends

Sort logs by timestamp, union() each pair in order, and track the shrinking group count — the timestamp where it first drops to 1 is the answer.

Medium