Union-Find (Disjoint Sets)

Keep track of which items belong to the same group, and merge groups quickly.

The idea (friend groups)

Imagine a party where people slowly become friends. You want to answer “are Ana and Raj in the same friend group?” and to merge two groups when their members meet. Union-find does both in almost constant time.

Every group is a tree, and the person at the top is the group’s root (its leader). The array parent[i] says who each person points to; a leader points to themselves.

Watch it work

Allowed: union A B and find A (items are numbered from 0). At most 15 operations.

Try it

Common mistakes

Complexity, in plain English: with union by size and path compression each operation is almost constant time (O(α(n)), where α grows so slowly it is below 5 for any input you will ever see). Memory is two small arrays.