Union-Find · Compound Engineer

Concept · Data structure

Intermediate · near-constant time per operation · O(n) space

Why it exists

Seven friends are not yet connected. Pairs of them become friends, one pair at a time, and after each pair we may be asked: are these two in the same circle? and how many circles are there?

The direct way is to run a graph search from one person after each new pair and see who it reaches. That costs O(V + E) for every question. With a million pairs and a million questions, we would search a million times.

Most of that work repeats. A new pair either joins two circles or lands inside one, and nothing else changes. Can we keep the circles up to date, instead of rediscovering them?

The core idea

Give each circle a leader, called its root. Every person stores one pointer, parent, to someone nearer the leader. The leader points to itself. Following the pointers from anyone always ends at their circle's leader.

Two people are in the same circle exactly when following their pointers ends at the same leader.

That gives two operations. Find climbs from a person to the leader. Union joins two circles by finding both leaders and hanging one leader under the other. The pointers form a forest: one tree per circle.

Two small tricks keep the trees short, which keeps find fast. Union by size always hangs the smaller tree under the bigger one. Path halving makes each person on the way up point at their grandparent, so the next climb is shorter.

A worked example

Seven people, numbered 0 to 6, and seven pairs arrive: (0,1) (2,3) (4,5) (1,3) (5,6) (3,0) (2,6). Teal circles are leaders, and an arrow points from a person to their parent.

Joining two single people. For (0,1), both are their own leaders and the groups have equal size, so 1 hangs under 0. The same happens for (2,3) and (4,5). Seven groups became four.

Joining two circles. For (1,3), the leaders are 0 and 2, each with 2 members. The sizes are equal, so 2 hangs under 0, and the circle of 0 now has 4 members.

A pair that adds nothing. For (3,0), climbing from 3 passes node 2 and ends at 0, and 0 is already a leader. Both people share a leader, so union returns false and nothing changes. In a graph, this is the pair that would close a cycle. While climbing, node 3 was also repointed straight at 0 by path halving.

The last merge. For (2,6), the leaders are 0 (4 members) and 4 (3 members). The bigger one stays on top, so 4 hangs under 0. Everyone is now in one circle of 7, and the count is 1.

How it works

Start with every node as its own parent and every size as 1. The group count is n.
Find(x): parent[x] is not x⟶point x at its grandparent, then climb. When parent[x] == x, return x.
Union(a, b): find both roots. same root⟶return False
different roots⟶hang the smaller tree under the bigger one, add the sizes, subtract 1 from the group count, return True

Why it is correct

The invariant is: following parents from any node ends at the root of that node's tree, and each tree is one circle. Find only climbs and shortens pointers: pointing a node at its grandparent keeps it inside the same tree. Union joins two different trees by a single pointer from one root to the other, so one tree becomes the union of both circles. Nothing else changes.

Why it is fast

Hanging the smaller tree under the bigger one means a node's depth grows only when its tree at least doubles in size, so depth is at most log₂ n. Path halving then flattens the trees further. Together the cost of each operation is O(α(n)), where α is the inverse Ackermann function. For any n you could ever store, α(n) is at most 4, so the cost is almost constant.

Watch it run

Pick an input, then press Play or use the arrow keys. The highlighted line is the one running, and the number beside each line counts how often it ran. The forest shows each person's parent as an arrow, and the two arrays show the same thing as numbers.

Complexity

O(α(n))

Time. Here's why: union by size keeps every tree at most log₂ n deep, and path halving shortens the paths further. With both, a sequence of m operations on n elements costs O(m × α(n)) in total, where α(n) ≤ 4 in practice. Building the structure costs O(n).

O(n)

Space. Two arrays of n numbers, parent and size, and one counter. No graph is stored.

Mistakes and variants

Linking the people, not the roots. Setting parent[a] = b directly moves only one person and leaves the rest of their circle behind. Always find the roots first.
No size rule. Without union by size, a bad order of pairs builds a tree that is one long chain, and find becomes O(n). Path halving alone still gives a good amortised cost, but the size rule makes it predictable.
Reading size of a non-root. A size is only meaningful at a root. After a union, the old root's size is stale.
Undoing a union. The structure cannot take a pair back. If you must undo, drop path halving, keep union by size, and push each union on a stack. Then find costs O(log n) instead.
Directed graphs. Union-Find answers "are these in the same group", which is symmetric. It cannot tell you whether you can get from a to b along one-way links.

Where it shows up

Reach for it when:

items are joined over time and you ask whether two are connected, or how many groups there are;
you must find the first link that closes a cycle in an undirected graph (union returns False);
you sweep through items in some order, such as increasing height, and join them as they become allowed.

Problems that use it:

Swim in Rising Water (join cells as the water reaches them)
Number of Islands (the follow-up where land appears one cell at a time)

Interviewer follow-ups

These are the questions that usually come next. Open one to see an answer you could say out loud.

"Why not just run a DFS after each new link?"

What they are checkingWhether you can say when Union-Find is worth its extra structure, instead of using it by reflex.

A strong answerIf I need one answer at the end, a single DFS is simpler and also O(V + E). Union-Find wins when the links arrive over time and I must answer in between: each question costs almost nothing, instead of a full O(V + E) search. It also wins when I process items in an order, like sorted by height, which does not fit a plain DFS.

"Is the path halving line necessary? What does it cost to leave it out?"

What they are checkingWhether you understand which trick gives which guarantee.

A strong answerUnion by size alone keeps every tree at most log n deep, so find is O(log n). That is already fine for most inputs. Path halving makes it faster in practice, getting the amortised cost down to near-constant. The one reason to leave it out is rollback: halving rewrites pointers, which makes undoing a union hard.

"Can you detect a cycle in an undirected graph with this?"

What they are checkingWhether you notice that union returning False carries information, instead of only treating it as a side effect.

A strong answerYes. Process the edges one by one. If union returns False, both ends were already connected, so this edge closes a cycle. If every union returns True, the graph is a forest. That runs in near-linear time and needs no recursion, so it is also safe for a very long chain.