Pattern visualizer

Accounts Merge

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. Animated on: 5 accounts (three "John", two "Mary") sharing 6 distinct emails through overlapping pairs — which accounts belong to the same person?.

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)step 1 / 10

5 accounts, 6 distinct emails

john00

john_ny

johnsmith

mary

john_sf

mary2

line 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.

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

Where to practice Graph

Practice Graph problems All Graph problems Back to roadmap