Accounts Merge
Merge the accounts that belong to one person, joined by any shared email, using union-find over emails and a final group-and-sort pass.
Problem Understanding
Accounts Merge (LeetCode 721): each account is a list whose first item is a name and whose other items are emails. Two accounts belong to the same person if they share at least one email. People can share a name, so a name alone never merges two accounts. Merge each person's accounts and return their emails in sorted order, with the name first. The accounts can come back in any order.
Example: [["John","johnsmith@mail.com","john_newyork@mail.com"],["John","johnsmith@mail.com","john00@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]] returns [["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]. The first two Johns share johnsmith@mail.com; the third John shares nothing and stays separate.
The Intuition: Emails Are the Nodes
Treat every email as a node. An account says all of its emails belong to one person, so it connects them. Two accounts that share an email end up in the same connected piece, even through a chain of other accounts. Each connected piece is one person.
- Register each email as its own set, and remember which name owns it.
- Union the account's first email with each of the others. That is enough to put the whole account in one set.
- Group by root. Emails with the same root belong to one person. Sort each group and put the name in front.
This is the same set-merging as Redundant Connection and Number of Provinces, with strings for nodes instead of numbers.
Interactive Walkthrough
GREEN = MERGED · COLOUR = PERSON
EMPTY MAPS
account
:
name
:
people
:
parent[email]
An empty parent map and owner map. Every email will start as its own set
Next
Account 1, John: js, jny. New emails js, jny start as their own sets. Now join js to the rest
accounts
The emails are shortened so they fit in a node: js stands for johnsmith@mail.com. Green edges are unions that merged two sets. In the grouping pass every email takes its person's colour. Try Already joined: the third account's union finds the same root and changes nothing.
Dry Run Table
Input: John: js, jny; John: js, j00; Mary: m; John: jb (the example above, with shortened emails).
| Account | New emails | Union | parent change |
|---|---|---|---|
| 1. John: js, jny | js, jny | find(js) = js, find(jny) = jny | parent[jny] = js |
| 2. John: js, j00 | j00 | find(js) = js, find(j00) = j00 | parent[j00] = js |
| 3. Mary: m | m | none (one email) | none |
| 4. John: jb | jb | none (one email) | none |
Grouping: js, jny and j00 have root js; m and jb are their own roots.
Result: [John, j00, jny, js], [Mary, m], [John, jb].
The Solution Template
Union-find keyed by email, with path halving in find(). The C version gives each distinct email a numeric id by sorting, which also leaves every group already sorted.
Accounts Merge Code
1var accountsMerge = function(accounts) {2 const parent = new Map();3 const owner = new Map();4 const find = (x) => {5 while (parent.get(x) !== x) {6 parent.set(x, parent.get(parent.get(x)));7 x = parent.get(x);8 }9 return x;10 };1112 for (const [name, ...emails] of accounts) {13 const first = emails[0];14 for (const email of emails) {15 if (!parent.has(email)) parent.set(email, email);16 owner.set(email, name);17 }18 for (const email of emails.slice(1)) {19 const a = find(first), b = find(email);20 if (a !== b) {21 parent.set(b, a);22 }23 }24 }2526 const groups = new Map();27 for (const email of parent.keys()) {28 const root = find(email);29 if (!groups.has(root)) groups.set(root, []);30 groups.get(root).push(email);31 }32 return [...groups].map(([root, emails]) => [owner.get(root), ...emails.sort()]);33};
Edge Cases & Common Mistakes
- Same name, different people: never merge on the name. Only a shared email joins two accounts.
- Account with one email: nothing to union; it still appears in the result, possibly merged through another account.
- Chains: A shares an email with B and B with C, but A and C share nothing. They are still one person, which union-find handles and a pairwise comparison of accounts misses.
- Unsorted output: each person's emails must be sorted; the name stays first and is not sorted with them.
- Duplicate emails across accounts: register an email once. Resetting its parent when it shows up again would undo earlier unions.
Summary
Every email is a node. Union each account's first email with the rest, then group the emails by root, sort each group and put the owner's name in front. O(E log E) time for the sort, O(E) space.
More practice: DSA interview questions with answers · patterns cheat sheet