Accounts Merge

Medium#721

You get a list of accounts: each is a name followed by emails. Two accounts belong to one person when they share an email, also through other accounts; one name does not make one person. Merge the accounts of each person and return each person as the name followed by all their emails, sorted. Our example: ["Ann", "ann@home", "ann@work"], ["Ann", "a.k@uni", "ann@work"], ["Ann", "ak@mail", "a.k@uni"], ["Ann", "ann@x"] → ["Ann", "a.k@uni", "ak@mail", "ann@home", "ann@work"], ["Ann", "ann@x"].

721 Accounts MergeWalkthrough · 1×

Example: ["Ann", "ann@home", "ann@work"], ["Ann", "a.k@uni", "ann@work"], ["Ann", "ak@mail", "a.k@uni"], ["Ann", "ann@x"]. All four are called Ann. Account 2 shares a.k@uni with account 1, and account 1 shares ann@work with account 0, so the three are one person; account 3 shares nothing.

012300112233parentownergroups—
looking at nowroot of a group of accounts

Each of the 4 accounts is its own root

01/75
restart · back · play · step
Speed
1function accountsMerge(accounts):
2 parent = [0, 1, ..., n - 1]
3 owner = empty map // email → first account with it
4 for each account i and each email of it:
5 if email not in owner:
6 owner[email] = i
7 else:
8 rootO = find(owner[email])
9 rootI = find(i)
10 if rootO is not rootI:
11 parent[rootI] = rootO
12 groups = empty map // root → set of emails
13 for i from 0 to n - 1:
14 root = find(i)
15 add emails of accounts[i] to groups[root]
16 return [name, sorted emails] for each group
17
18function find(x):
19 while parent[x] is not x:
20 x = parent[x]
21 return x
state
parent
[0, 1, 2, 3]
i
–
email
–
rootO
–
rootI
–
root
–
x
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Accounts are the items of the union-find. owner keeps the first account of every email, so an email seen again links the account to that first one, and links never break.
  2. Joining is catching: account 2 meets account 1, which is already under account 0, so all three end up under one root without account 2 ever meeting account 0.
  3. Grouping by the root of each account puts every email of a person in one place; the set drops the repeats, and only the name is taken from the account.

Complexity

Time O(E · h + E log E) for E emails in all: up to two finds per email, as deep as the trees (up to the number of accounts here, almost a constant with re-hanging on the root and the smaller tree under the bigger), and the sort. Memory O(E) for owner and groups.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.