Accounts merge

Hard

Union accounts through shared emails

Problem

Merge accounts that share any email into single accounts (union-find on emails).

In simple words

Emails that appear together belong to one person; union them and group the results.

The idea

Map every email to the first account index that mentioned it and union accounts whenever an email reappears. Grouping the emails by their component root and sorting each group produces the merged accounts.

The trick

Union on the account index, keyed by email.
Names come from any account in the component — they are all the same person.
Emails must be sorted within each merged account.

←→stepspaceplay

1/10

Optimal

timeO(α(n))spaceO(n)

Almost constant per op.

1function find(x) {2  while (p[x] !== x) { p[x] = p[p[x]]; x = p[x]; }3  return x;4}5function union(a, b) {6  a = find(a); b = find(b);7  if (a === b) return false;8  if (rank[a] < rank[b]) [a, b] = [b, a];9  p[b] = a; if (rank[a] === rank[b]) rank[a]++;10  return true;11}

Input

nodes: 5, 0 edges

Memory

groups: —

Output

groups: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Example

Input:: accounts with shared emails
Output:: merged accounts

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.