Accounts Merge
Problem
Each account is [name, email1, email2, …]. Two accounts belong to the same person if they share any email (names alone prove nothing). Merge them and return each person as [name, …their emails sorted].
Example 1
Input: [["John","a@x","b@x"], ["John","c@x"], ["John","b@x","d@x"], ["Mary","m@x"]] Output: [["John","a@x","b@x","d@x"], ["John","c@x"], ["Mary","m@x"]]
Test cases
Case 1
Input: [["John","johnsmith@mail.com","john_newyork@mail.com"],["John","johnsmith@mail.com","john00@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]] Expected (any order): [["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]
Case 2
Input: [["A","a@x.com","b@x.com"],["B","c@x.com"],["A","b@x.com","d@x.com"]] Expected (any order): [["A","a@x.com","b@x.com","d@x.com"],["B","c@x.com"]]
Case 3
Input: [["A","a@x.com"]] Expected (any order): [["A","a@x.com"]]
View solutionHide solution1 approach
1. Union-Find over emails
Time O(N log N) — N total emails, dominated by sortingSpace O(N)
Union every email in an account with that account’s first email. Group emails by root, sort each group, prefix the owner’s name.
function accountsMerge(accounts) { const parent = new Map(), owner = new Map(); const find = (x) => { if (parent.get(x) !== x) parent.set(x, find(parent.get(x))); return parent.get(x); }; for (const [name, ...emails] of accounts) { for (const e of emails) { if (!parent.has(e)) parent.set(e, e); owner.set(e, name); parent.set(find(e), find(emails[0])); } } const groups = new Map(); for (const e of parent.keys()) { const r = find(e); if (!groups.has(r)) groups.set(r, []); groups.get(r).push(e); } return [...groups.values()].map((g) => [owner.get(g[0]), ...g.sort()]);}