Skip to content

level 7 · Graphs

Union-Find

Merge groups and ask 'are these two connected?' — in effectively constant time.

12 min 100 XP

what is it

Start here

Union-Find does exactly two things: merge two groups, and answer 'are these two things in the same group?'. That's it. And it does both so fast that the cost is, for all practical purposes, constant.

The idea is beautifully cheap. Every item points at a parent. Follow the parents up and you reach a root — and **the root is the group's identity**. Two things are in the same group if and only if they climb to the same root. To merge two groups, you don't touch their members at all: you just hang one root under the other. One pointer, and two entire groups become one.

Left alone, though, those trees can grow into long chains, and climbing them gets slow. So there are two fixes, and together they're the whole magic.

**Union by rank**: always hang the shorter tree under the taller one, so the trees stay stubbornly flat instead of stringing out.

**Path compression**: every time you climb to the root, re-point every node you passed *straight at the root*. The next lookup is a single hop. The structure literally teaches itself to be faster each time you use it.

Together, the amortised cost is the inverse Ackermann function — a function that grows so unimaginably slowly it is under 5 for any input that will ever exist in this universe. It is not technically O(1). You may treat it as O(1).

real-life analogy

Picture it

Everyone points at their boss

To find which company you're in, keep asking 'who's your boss?' until you reach someone who's their own boss — that's the CEO, and the CEO identifies the company. To merge two companies, one CEO starts reporting to the other. Nobody else's paperwork changes. And on the way up, everyone you passed just starts reporting to the CEO directly — so next time it's one question, not ten.

interactive visualization

Watch it run

Arrows are parent pointers — the forest IS the data structure.

0
1
2
3
4
5
6
7

Eight things, and nobody is connected to anybody — 8 separate groups. Each one points at itself, so each one is its own boss. The arrows you'll see are parent pointers: they *are* the data structure.

step 01/18

  • just discovered
  • moving
  • visited
  • visiting now
  • ruled out
1const parent = [...Array(n).keys()]; // everyone is their own boss
2const rank = new Array(n).fill(0);
3
4function find(x) {
5 if (parent[x] !== x) {
6 // Path compression: point straight at the boss on the way back.
7 parent[x] = find(parent[x]);
8 }
9 return parent[x];
10}
11
12function union(a, b) {
13 const ra = find(a), rb = find(b);
14 if (ra === rb) return false; // already together
15
16 // Union by rank: hang the shorter tree under the taller one.
17 if (rank[ra] < rank[rb]) parent[ra] = rb;
18 else if (rank[ra] > rank[rb]) parent[rb] = ra;
19 else { parent[rb] = ra; rank[ra]++; }
20
21 return true;
22}

variables right now

items
8
groups
8
comparisons 0moves 0

the dry run · every step, in words

18 steps

complexity

What it costs

best case
O(1)
average
O(α(n))
worst case
O(α(n))
extra memory
O(n)

α is the inverse Ackermann function, which is below 5 for any n that could physically exist. Not technically O(1) — but you may treat it as constant with a completely clear conscience. Without the two optimisations it would degrade to O(n) per operation.

  • O(1) · this one
  • O(log n)
  • O(n)
  • O(n log n)
  • O(n²)
input size →work →

common mistakes

Common traps

  • Skipping path compression.

    Without it, the trees grow into long chains and every find() walks them. It's two lines of code and it's most of the performance.

  • Hanging the taller tree under the shorter one.

    That deepens the tree for no reason. Union by rank always puts the shorter under the taller, keeping everything flat.

  • Comparing the two items directly instead of their roots.

    Two items in the same group usually have different parents. Sameness is decided at the *root* — always compare find(a) with find(b).

  • Trying to un-merge two groups.

    You can't. Union-Find is one-way — it merges, and it cannot split. If you need to remove connections, you need a different structure entirely.

quiz

Check yourself

Three questions. Get them all right to finish the lesson.

+100 XP

01How do you tell whether two items are in the same group?

02What does path compression do?

03What can Union-Find NOT do?

practice

Solve it on LeetCode

You've seen it run — now write it yourself. These are real LeetCode problems that use exactly this idea, from gentlest to toughest.