Union-find
Are these two things connected yet?
Sixteen seconds of work every second
A risk engine links accounts that share a phone number, a device or a bank account. About 3 million links arrive in a day, and between them the engine answers one question, 200 times a second: are these two accounts the same person?
The first version keeps the links as a graph and answers each question with a BFS. The answers are right. Now work out the time. The busiest linked group holds 40,000 accounts, and a BFS through it takes about 80 ms. At 200 questions a second, that is 16 seconds of work arriving every second. The queue in front of the engine grows by the minute, and payments wait on it.
Look at what one of those searches does. It finds a whole path between the two accounts, phone to device to bank account to phone, and then uses one bit of all that work: yes, they are linked. No caller ever asks how two accounts are linked, only whether they are.
Pause and predict If you stop caring how accounts are linked, what is the one thing to keep for each account?
Every group has one name
Edges arrive one at a time, and between them someone asks: are these two connected yet? A BFS answers the question once, then has to start over after the next edge arrives. You want a structure that takes in each edge in close to O(1) time and answers each question in close to O(1) time.
The key step is to stop recording how things are connected and keep only which group each thing is in. Union-find stores each group as a tree in a parent array: each node stores its parent, and a root is a node whose parent is itself. The root serves as the name of its group. find(x) walks up to the root. union(a, b) makes one root the parent of the other.
Why it stays fast
The rule above does not say which root goes under which. If you choose badly, a tree can become one long line, and every find walks all of it.
Pause and predict 1,000 nodes are joined into a line by union(i, i + 1), with find(0) after each union, and no optimisations. Roughly how many parent pointers do the finds follow in total?
Union by size: the smaller tree goes under the larger root. A node gets one level deeper only when its tree at least doubles, and a tree can double at most log2(n) times. So no node is ever more than log2(n) hops from its root.
Path compression: after find walks from x to the root, it points every node on that path straight at the root. Those nodes were already in that tree, and the root did not change, so no answer changes; only later walks get shorter.
Together they cost O(α(n)) amortised per operation. α is the inverse Ackermann function, and it is at most 4 for any n you could store. The proof is long. In an interview, say "near constant", and know what happens if you remove either rule. The counts below come from running each version on that bad sequence of unions.
The same grouping decides where data lives. Union every pair of keys that one transaction touches, and each resulting group can live on one shard, so no transaction ever has to commit across shards.
How to recognise it
The sign is connectivity that only grows: edges, friendships, shared emails or equalities that arrive over time. The questions are "are these two in the same group?" and "how many groups are there now?".
Pause and predict Links between accounts can also be deleted. Is union-find still the tool?
Three that only look like it
- When the question is about paths, distances or the order of a walk, use BFS or DFS. Union-find does not keep the edges that connect a group.
- When the edges are directed dependencies, use topological sort. Union-find ignores direction, so it would only record that a course and its prerequisite are connected.
- When edges can disappear, union-find cannot split a group. Recompute, or process the queries backwards.
Where it bites
Pause and predict parent[3] = 2, parent[2] = 0, parent[5] = 0, and 0 is a root. Are 3 and 5 in the same group?
- Forgetting the optimisations. Without them, linking can build a long line that every find has to walk: O(n) per call, and O(n²) over n calls. Path compression and union by size take two lines of code, so always write both.
- Linking nodes instead of roots.
parent[b] = amoves b out of its tree and leaves the rest of that tree behind. - Comparing parents instead of roots. Two nodes in one tree can have different parents. Always compare
find(a)withfind(b). - Counting every union as a merge. Only a union that returns true merges two components.
- Nodes numbered from 1. Redundant Connection numbers nodes 1 to n, so the arrays need n + 1 slots.