Accounts Merge

Medium

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"]]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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()]);
}