Accounts Merge
Accounts Merge is LeetCode 721 (Medium). You get a list accounts, where each entry is a name followed by that account's emails. Merge the entries that belong to the same person.
- Two accounts belong to the same person if they share at least one email, and that link chains: A with B and B with C puts all three together.
- A name alone proves nothing. Two different people may both be called John.
- Each merged account is the name followed by all of its emails in sorted order, and the groups may be returned in any order.
There are up to 1000 accounts of at most 10 emails each, so the work is dominated by sorting the merged groups rather than by the merging itself.
- 1 <= accounts.length <= 1000
- 2 <= accounts[i].length <= 10
- 1 <= accounts[i][j].length <= 30
- accounts[i][0] consists of English letters.
- accounts[i][j] (for j > 0) is a valid email.
Intuition
Forget the accounts and look at the emails. Two emails that appear in the same account belong to the same person, and that link spreads: if a and b share an account and b and c share another, all three are one person even though a and c never met.
That is exactly connected components, and union find accounts merge is the standard answer: union-find keyed on the emails builds them in one pass. Union every email in an account with that account's first email, and the components fall out no matter what order the accounts arrive in. The name rides along in a side map, because it identifies nothing.
Whenever things have to be grouped by a "shares something with" rule that chains through intermediaries, you are looking at connected components, and union-find is the direct tool. The move that makes it easy is picking the right node: union the shared token itself, here the email, rather than the records that contain it.
Approach
Before reading on, take three accounts where the first and third share no email but both share one with the second. Work out by hand why they still belong together, and what you would key a union-find on to get that for free. Aim for O(N log N) time.
Union every email with the account's first
Walk the accounts, and for each one union all of its emails with its first email. That links the whole account into one component in a single pass, and because union-find merges by root, two accounts sharing any email end up in the same component without you having to find the overlap yourself.
Key the structure on emails, never names
The nodes are the email strings. A name is not an identity: two different people called John must stay apart, and they will, because nothing ever unions their emails. Using names as keys merges strangers together.
Remember each email's owner on the side
While scanning, store owner[email] = name in a plain map. Every email belongs to exactly one person, so whichever email you later pick from a finished group hands back the right name to print.
Group the emails by their final root
Once all the unions are done, call find on every email and bucket it under the root that comes back. Doing this only at the end matters: a root found mid-scan may still be merged into another later, so the grouping has to wait.
Sort each group and put the name in front
The required row is the name followed by the emails in alphabetical order:
- sort inside each group, not across everything.
- keep the name out of the sort – it is a label on the row, not one of the sorted values.
Accounts Merge solution in Python | C++ | Java
find once and bucketed under the root it lands on. The grouping has to wait until the end, because a root found earlier may itself have been merged into another since.find once and bucketed under the root it lands on. The grouping has to wait until the end, because a root found earlier may itself have been merged into another since.Common pitfalls
Uniting by name
union(name, e)
union(emails[0], e)
Different people share names — the problem explicitly warns of this. Only a shared email proves two accounts belong to the same person, so emails must be the union-find keys.
Grouping by the account's index
groups.setdefault(find(i), []).append(...)
groups.setdefault(find(e), []).append(e)
Two accounts merge only through their emails, so the component root is an email. Keying groups by account index produces separate entries for accounts that should have merged.
Not sorting the emails
result.append([owner[emails[0]]] + emails)
result.append([owner[emails[0]]] + sorted(emails))
The expected output requires each account's emails in sorted order after the name. Union-find yields them in arbitrary traversal order, so the sort is a required final step.
Edge cases
Nothing ever unions their emails, so they stay in separate groups and both rows carry that name.
Its emails form their own component and come back as a single group, unchanged apart from the sort.
A merges with B and B with C, so all three land under one root even though A and C share nothing directly.