Union-Find & Artist Dedupe
Three labels uploaded the same artist three times: theweeknd, the-weeknd and
weeknd-official. Moderators report duplicates one pair at a time — "theweeknd is
weeknd-official", then later "the-weeknd is theweeknd" — and Tunebox has to merge
them transitively, then answer "are these the same artist?" instantly while
reports keep arriving. Re-walking a graph for every question is too slow.
Union-find (also called a disjoint-set) merges groups and answers that
question in effectively constant time.
Every group has a representative
Union-find keeps a set of separate groups. Each group has one member chosen as its representative, or root, and every element holds a parent pointer leading toward it. At the start nobody has been merged, so everyone is their own parent:
A root is exactly an element whose parent is itself.
find — follow the pointers to the root
To learn which group something is in, follow parent pointers until you reach an element that points at itself:
parent = {"adele-music": "adele-hq", "adele-hq": "adele", "adele": "adele", "sza": "sza"}
def find(x):
while parent[x] != x:
x = parent[x]
return x
print(find("adele-music"), find("sza"))Two elements are in the same group exactly when find gives the same root.
union — hang one root under the other
Merging two groups is one pointer change: make one root the parent of the other root. Link the roots, not the elements you were handed — this version gets that wrong:
All three profiles were reported as the same artist, so this should print True. It prints False. Fix union so merging never undoes an earlier merge.
Link roots and every earlier merge survives, because you only ever change a pointer that used to point at itself.
❓ Cross-question — "Why not store the matches as a graph and run DFS?" For one question on a fixed graph, that's fine. But DFS costs O(V + E) per question, and matches keep arriving between questions. Union-find handles an interleaved stream of merges and questions at almost O(1) each — and it never needs the edges again once they're merged.
Path compression
A long chain of parents makes find slow. Path compression fixes it while you
walk: once you know the root, point every element you passed through straight at
it. The next find on any of them is a single hop.
parent = {"d": "c", "c": "b", "b": "a", "a": "a"}
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
find("d")
print(parent["c"])Union by rank
Compression repairs tall trees after the fact; union by rank avoids building them. Give each root a rank — an upper bound on its tree's height — and always hang the lower-ranked root under the higher one. Only when two ranks tie does the height grow, by one. Step through three merges:
Together, the two tricks make a class worth keeping:
The iterative find does the same flattening as the recursive one, without any
recursion depth to worry about.
| Version | Cost per find / union |
|---|---|
| Plain parent pointers | O(n) worst case — one long chain |
| Union by rank only | O(log n) |
| Path compression only | O(log n) amortized |
| Both together | O(α(n)) amortized — effectively constant |
| Kruskal's MST (below) | O(E log E) — dominated by the sort |
Coming from Java/JS: textbook union-find uses
int[] parentindexed by element number. With string ids, a dict gives you the same thing without first mapping names to integers.
Kruskal's minimum spanning tree
Tunebox wants to link its offices with private cables. Each possible cable has a price; the goal is to connect every office for the lowest total. That's a minimum spanning tree, and Kruskal's algorithm builds it greedily: sort the cables cheapest first, and keep each one only if it joins two groups that aren't connected yet. Union-find answers "already connected?" at almost no cost.
A cable whose ends already share a root would only close a loop, so it's skipped. With V offices, the tree is finished after exactly V − 1 kept cables.
Idioms & real-world patterns
Let union report whether it merged
Returning True/False from union turns common questions into one-liners. Count
the groups: start at n, subtract one per successful union. Spot a loop in an
undirected graph: the first edge whose union returns False joins two things that
were already connected.
Picking a readable representative
The root is whichever element the unions happened to leave on top — fine internally, but arbitrary to show a user. When you need a stable answer, choose one after merging: group elements by root, then take, say, the alphabetically first name in each group.
⚡ Advanced — how constant is "effectively constant"?
α(n) is the inverse Ackermann function. It grows so slowly that α(n) ≤ 4 for any n
you could ever store. The bound is amortized: an individual
find can still walk a few steps, but no long sequence of operations averages worse.
⚡ Advanced — what union-find can't do
It only merges. There's no cheap way to split a group again — un-merging a wrongly reported duplicate means rebuilding from the remaining matches. When deletions matter, systems keep the match list as the source of truth and rebuild the sets offline.
🎯 Your turn
Write merge_duplicates(profiles, matches). profiles lists artist profile names;
matches holds [a, b] pairs a moderator marked as the same artist, and sameness is
transitive. Return a dict mapping every profile to the name its group collapses
into — the alphabetically first name in that group:
merge_duplicates(["adele", "adele-music", "sza"], [["adele-music", "adele"]])→{"adele": "adele", "adele-music": "adele", "sza": "sza"}merge_duplicates([], [])→{}
Hint — union every match, then walk the profiles in sorted order: the first name you meet for each root is that group's canonical name.
Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green = this piece of the app is built. ✅