The problem. Each account is a list: a name, then some email addresses. Two accounts belong to the same person if they share any email — directly, or through a chain of other accounts. Two people can have the same name. Merge the accounts so each person appears once: their name followed by all of their emails, sorted. The people can be returned in any order.
accounts = [["John","js@m","jny@m"],
["John","js@m","j00@m"],
["Mary","mary@m"],
["John","jb@m"]]
-> [["John","j00@m","jny@m","js@m"],
["Mary","mary@m"],
["John","jb@m"]]Think of every email as a vertex, with an edge between two emails that appear in the same account. One person's emails are then exactly one connected piece of that graph: a shared email is the bridge between two accounts. So the job is: find the pieces, then print each piece with its owner's name, sorted.
Finding pieces is what both earlier tools do. DFS walks each piece. Union-Find merges groups as the links appear — and here it's natural to merge whole accounts: the first account to list an email "owns" it, and any later account listing the same email is merged with the owner.
You don't need an edge between every pair of emails in an account — joining each one to the account's first email is enough to connect them all.
Link every email to its account's first email, remember each email's name, then walk each connected piece once.
function accountsMerge(accounts) { const graph = new Map(); // email -> emails it is linked to const name = new Map(); // email -> owner's name const link = (a, b) => { if (!graph.has(a)) graph.set(a, []); graph.get(a).push(b); }; for (const [owner, ...emails] of accounts) { for (const email of emails) { name.set(email, owner); link(email, emails[0]); // join every email to the account's first one link(emails[0], email); } } const seen = new Set(); const result = []; for (const start of graph.keys()) { if (seen.has(start)) continue; const group = []; // one connected piece = one person const stack = [start]; seen.add(start); while (stack.length > 0) { const email = stack.pop(); group.push(email); for (const next of graph.get(email)) { if (!seen.has(next)) { seen.add(next); stack.push(next); } } } result.push([name.get(start), ...group.sort()]); } return result;}Time O(E log E), space O(E). E is the total number of emails. Building the graph and walking it are linear; sorting each person's emails is the slowest part.
Give each account its own group. Walk the emails: the first account to list an email becomes its owner; a later account listing it is merged with the owner's group. Then put every email into the group of its owner's root, and sort.
Shared emails merge account groups; then every email joins its owner's root. Try two people with the same name.
function accountsMerge(accounts) { const parent = accounts.map((_, i) => i); // one group per account to start const find = (x) => { while (parent[x] !== x) { parent[x] = parent[parent[x]]; // path halving x = parent[x]; } return x; }; const owner = new Map(); // email -> first account that listed it accounts.forEach((account, i) => { for (const email of account.slice(1)) { if (owner.has(email)) parent[find(i)] = find(owner.get(email)); // shared email: same person else owner.set(email, i); } }); const groups = new Map(); // root account -> all of its emails for (const [email, i] of owner) { const root = find(i); if (!groups.has(root)) groups.set(root, []); groups.get(root).push(email); } return [...groups].map(([root, emails]) => [accounts[root][0], ...emails.sort()]);}Time O(E log E), space O(E). Each email costs one map lookup and at most one union — practically constant — and sorting dominates again. Path halving alone keeps find fast here; union by size would tighten the guarantee further.
Both are standard answers. Union-Find skips building an explicit graph, and it shines when accounts keep arriving — it can merge them on the fly, which a DFS would have to redo.