721. Accounts Merge

Each account is [name, ...emails]. Two accounts belong to the same person if they share any email. Merge them and return each person's name followed by their emails in sorted order.

Give each account an id. When an email was already seen in another account, union the two accounts. Finally group emails by their account's root.

1function accountsMerge(accounts: string[][]): string[][] {
2  const parent = accounts.map((_, i) => i);
3  const find = (x: number): number => (parent[x] === x ? x : (parent[x] = find(parent[x])));
4  const owner = new Map<string, number>();
5  accounts.forEach(([, ...emails], i) => {
6    for (const e of emails) {
7      if (owner.has(e)) parent[find(i)] = find(owner.get(e)!);
8      else owner.set(e, i);
9    }
10  });
11  const groups = new Map<number, string[]>();
12  for (const [e, i] of owner) {
13    const r = find(i);
14    if (!groups.has(r)) groups.set(r, []);
15    groups.get(r)!.push(e);
16  }
17  return [...groups].map(([r, es]) => [accounts[r][0], ...es.sort()]);
18}

accounts (edges = shared email)

parent

owner (email → account)

empty

Each account is its own set.

1 / 0

Space: play/pause · ←/→: step