Union–Find (disjoint sets)
find with path compression, union by size; components merge in near O(1).
Two nodes share a root iff they are connected.
01The intuition
Start with what you would do by hand
A class has 4 students, numbered 1 to 4. Friendships are announced one at a time: (1,2), (3,4), (1,3), (2,3). After each announcement you want to know: are these two already in the same friend group? For (2,3) the answer is yes: 2 is friends with 1, 1 with 3. That announcement is redundant.
By hand you keep a list of groups and merge two lists when a friendship connects them: {1,2} {3,4} → {1,2,3,4}. Merging means rewriting everyone's group label. With 4 students that is nothing. With a million users and a million friendships, relabelling a group of half a million people on every merge is far too slow.
Build the structure, one piece at a time
Step one: instead of a label, each student remembers one parent. A group is a tree, and the root of the tree (whose parent is itself) stands for the whole group. Start with everyone as their own root:
| x | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| parent[x] | 1 | 2 | 3 | 4 |
Step two, find: to learn someone's group, follow parents until you reach a root. find(2) = 2 at the start.
Step three, union: to merge two groups, find both roots and make one root the parent of the other. Nobody else is touched. After (1,2): parent[2] = 1. After (3,4): parent[4] = 3. After (1,3): parent[3] = 1. Now parent = [1, 1, 1, 3]. Announcement (2,3): find(2) = 1, find(3) = 1, same root, so it is redundant.
Step four, two small tricks so trees stay shallow. Union by size: attach the smaller tree under the larger, so a tree's height grows only when it at least doubles in size. Path compression: after a find, point every node you walked over directly at the root, so the next find is one hop.
Why it is correct
The invariant: two students have the same root if and only if a chain of announced friendships connects them. Union preserves it: linking root A under root B joins exactly the two groups whose members have roots A and B, and nobody else changes root. Path compression preserves it too: it changes parents but never which root a node reaches.
Why it is fast
With union by size, a node's root is at most log2 n hops away, because every time its depth grows by one its tree at least doubles:
height ≤ log2 n, so one find ≤ log2(106) ≈ 20 hops
Path compression then flattens the trees as you go, and the proven bound becomes α(n) per operation, the inverse Ackermann function, which is at most 4 for any input you will ever meet. A million operations cost a few million steps, against the trillions a relabelling approach could spend.
How to recognise it in an interview
Cues: "connected", "same group", "merge accounts", "how many provinces or components", edges arriving one by one with questions in between, "the first moment everyone is connected". The first thing to say: "I will keep a disjoint-set forest and check whether the two endpoints share a root." Redundant Connection is the example above: the first edge whose endpoints already share a root is the answer. Accounts Merge unions accounts that share an email, then groups by root. Number of Provinces counts how many roots remain.
02The idea in one line
find with path compression, union by size; components merge in near O(1).
Reach for it when: Provinces, redundant connection, accounts merge, valid tree, earliest friendship.
Cost: O(α(n)) per op.
03The walk-through, step by step
The video works one example: Redundant Connection on edges [1,2],[1,3],[2,3]. These are its captions in order, so you can follow without the video or check a step you missed.
- Every node starts as its own set: parent[x] = x
- Edge (1,2): find(1) = 1, find(2) = 2
- Different roots: union, parent[2] = 1
- Edge (3,4): find(3) = 3, find(4) = 4
- Different roots: union, parent[4] = 3
- Edge (1,3): find(1) = 1, find(3) = 3
- Different roots: union, parent[3] = 1
- Edge (2,3): find(2) = 1, find(3) = 1
- Same root: 2 and 3 already connected, so (2,3) is redundant
- find with path compression + union by size: near O(1) per op
04Asked at Google
12 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.
| Problem | Difficulty | Frequency | Reported |
|---|---|---|---|
| The Earliest Moment When Everyone Become Friends | Medium | 43 | last 6 months |
| Number of Provinces | Medium | 40 | last 6 months |
| Accounts Merge | Medium | 37 | last 6 months |
| Number of Islands II | Hard | 36 | |
| Evaluate Division | Medium | 36 | last 6 months |
| Redundant Connection | Medium | 36 | last 6 months |
| Graph Valid Tree | Medium | 28 | |
| Number of Connected Components in an Undirected Graph | Medium | 22 | |
| Similar String Groups | Hard | 22 | |
| Most Stones Removed with Same Row or Column | Medium | 21 | last 6 months |
| Satisfiability of Equality Equations | Medium | 18 | last 6 months |
| Smallest String With Swaps | Medium | 17 |
05Related patterns
Other patterns in Graphs: Grid flood fill (components), Multi-source BFS, BFS shortest path (unweighted), BFS over an augmented state, 0-1 BFS (deque), DFS three-colour cycle detection, Topological sort (Kahn's), Dijkstra (weighted shortest path), Bellman–Ford with k rounds, Minimum spanning tree, Bipartite colouring, Eulerian path (Hierholzer), Bridges / articulation (low-link), Clone / traverse with a visited map, Implicit graph (states as nodes).