DSA Tracker

Visualize

Accounts Merge

Union-find over emails: shared addresses chain accounts into one person

time O(N*K*α(N*K) + N*K log(N*K))space O(N*K)

Two accounts belong to the same person exactly when they share an email, directly or through a chain of shared emails — names can repeat and can't be trusted. Treat every email as a node and union it with the other emails in its own account, always anchored on that account's first email. After every account has been folded in, every email with the same union-find root is the same person's address: group by root, sort each group, and attach the name. The picture below adds one edge per account (first email to each other email) and highlights which union just ran.

Details

Animated on: 5 accounts (three "John", two "Mary") sharing 6 distinct emails through overlapping pairs — which accounts belong to the same person?

Problem:Accounts MergeMedium

Union-find over emails: shared addresses chain accounts into one person

step 1 / 10

5 accounts, 6 distinct emails

Names alone don't tell you who owns which account — two entries can both say "John". The only trustworthy signal is a SHARED EMAIL: whenever two accounts list the same address, they belong to the same person, even through a chain of shares.

Pseudocode
1FUNCTION accountsMerge(accounts):
2  FOR EACH account IN accounts
3    first <- account.emails[0]
4    FOR EACH email IN account.emails[1:]
5      UNION(first, email)
6    nameOf[first] <- account.name
7  FOR EACH email IN allEmails
8    root <- FIND(email)
9    APPEND email TO groups[root]
10  FOR EACH root IN groups
11    sorted <- SORT(groups[root])
12    APPEND [nameOf[root]] + sorted TO result
13  RETURN result

← / → step · space play · Home restart

Every step in words

Show all 10 steps
  1. Names alone don't tell you who owns which account — two entries can both say "John". The only trustworthy signal is a SHARED EMAIL: whenever two accounts list the same address, they belong to the same person, even through a chain of shares.
  2. Account 1 ("John") lists john00@... and john_ny@... together, so UNION merges them. That group is now {john00, john_ny} — 2 addresses.
  3. Account 2 ("John") lists john00@... and johnsmith@... together, so UNION merges them. That group is now {john00, john_ny, johnsmith} — 3 addresses.
  4. Account 3 ("Mary") lists only mary@... — nothing to union it with yet, so it stays its own group of one until something else shares that address.
  5. Account 4 ("John") lists johnsmith@... and john_sf@... together, so UNION merges them. That group is now {john00, john_ny, johnsmith, john_sf} — 4 addresses.
  6. Account 5 ("Mary") lists mary@... and mary2@... together, so UNION merges them. That group is now {mary, mary2} — 2 addresses.
  7. Follow every UNION back and john00, john_ny, johnsmith, john_sf all share one root — 4 addresses for one person, even though john_ny@... and john_sf@... were never in the same account. The chain through john00@... and johnsmith@... connects them.
  8. mary and mary2 form a second, separate group — nothing connects them to John's emails, so they stay 2 distinct components worth of one person.
  9. Sorting john00@...'s group alphabetically gives [john00, john_ny, john_sf, johnsmith] — the order the answer requires, computed once per group instead of once per account.
  10. 5 accounts collapse into 2: one "John" entry with 4 emails and one "Mary" entry with 2. RETURN result.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Accounts Merge in the editorAll Graph problemsBack to roadmap