Union-Find

Answering "are these two in the same group?" in almost constant time.

The idea

Union-Find — also called a disjoint-set union, or DSU — does exactly two things: merge two groups, and answer whether two elements are in the same group.

The whole structure is one array. parent[i] holds the index of i's parent, and an element that is its own parent is the root of its group. Two elements belong to the same group when following parents from each leads to the same root.

That is the entire idea. The cleverness is in keeping the chains short.

Path compression: after finding a root, point every node you walked past straight at it. The next query on any of them is one hop.

Union by size or rank: when merging, hang the smaller tree under the larger one, so the depth grows as slowly as possible.

With both, the amortised cost per operation is the inverse Ackermann function — under 5 for any input that fits in the universe. It is not technically O(1), and it is close enough that treating it as constant is fair.

What it cannot do is tell you how two elements are connected. There is no path, no distance, no ordering. If you need any of that, you need a graph traversal.

Walkthrough

The parent array is the structure. Watch each element get repointed straight at its root — that write is path compression, and it is why the next query is one hop.

What it costs

time: O(α(n)) amortised per union or find — effectively constant
space: O(n) for the parent array, plus O(n) if you track sizes

α is the inverse Ackermann function, which is below 5 for any n you can store. Without path compression and union by size, a bad merge order degrades this to O(n) per operation.

When to reach for it

The question is only "same group or not?", asked many times as groups merge.
Connections arrive incrementally and you need connectivity after each one.
You are counting connected components, detecting a cycle while adding edges, or running Kruskal for a minimum spanning tree.
Grid problems about islands or regions, where each cell unions with its neighbours.

Rather than the obvious alternative

BFS or DFS over a graph

A traversal recomputes connectivity from scratch each time — O(V + E) per query. Union-Find answers each in near-constant time. Choose the traversal when you need the actual path or distance, which Union-Find cannot give you.

A hash map of group id to members

Merging two groups means rewriting every member of one of them, which is O(n) per union. Union-Find changes a single pointer.

How to spot it

The problem merges things and asks about membership, never about routes.
Edges arrive one at a time and each one may join two groups.
You are asked to count groups, or to find the edge that first connects everything.
Adding an edge between two nodes already in the same group would create a cycle — and detecting that is the question.

Where it goes wrong

Comparing elements instead of roots

Two elements are in the same group when their *roots* match. Comparing the elements themselves, or their immediate parents, silently reports the wrong answer for anything deeper than one level.

Union without find

`parent[a] = b` merges the wrong things unless a and b are already roots. Always find both roots first, then link one root to the other.

Skipping the balancing

Path compression alone is usually enough in practice, but unioning without regard to size can build a chain, and a chain is a linked list with extra steps.

Try it

Two short checks. They run the same way the practice problems do — write the function, press Run.

Given a parent array, return true if a and b share a root. Follow parents until an element is its own parent.

Or press ⌘↩

Tests

4 cases, 1 hidden

call	type	expected	result
sameGroup([0,0,2], 0, 1)	same group, one hop	true	—
sameGroup([0,0,2], 1, 2)	different groups	false	—
sameGroup([0,0,2], 2, 2)	same element	true	—
withheld	hidden	withheld	—

Hidden cases run too — their inputs aren't listed here, so aim for a general solution rather than one fitted to the cases above.

Hints

Stuck? Hints open one at a time, each giving a little more away.

2 hints left