Accounts Merge By Email
Problem
Each account is a name followed by one or more email addresses. Two accounts belong to the same person when they share at least one email, and that sharing is transitive: A shares with B and B with C means all three are one person. Merge them, and return each person as their name followed by all their emails in sorted order. Different people may have the same name.
Examples
Input: [["Jo", "a@x", "b@x"], ["Jo", "b@x", "c@x"], ["Kim", "d@x"]]
Output: [["Jo", "a@x", "b@x", "c@x"], ["Kim", "d@x"]]
Why: the two Jo accounts share b@x, so they are one personInput: [["Jo", "a@x"], ["Jo", "z@x"]]
Output: [["Jo", "a@x"], ["Jo", "z@x"]]
Why: the same name with no shared email is two different peopleInput: [["Kim", "d@x"]]
Output: [["Kim", "d@x"]]
Why: edge case, a single account merges with nothingHints
0 / 3
Names cannot drive the merge, because two people may share one. The emails are the only reliable identity.
Transitive sharing is the giveaway: this is a grouping question over emails, not a pairwise comparison of accounts.
Treat every email as an element of a disjoint-set structure. Within one account, join all its emails to the first one. Afterwards, bucket every email by its representative and attach the name recorded for it.
Solution
Emails are the elements; an account is just an instruction to join its own emails together. After one pass the sets are exactly the people, whatever order the accounts arrived in. A second pass buckets each email under its representative, and the name is carried along on any email of the group since every account in a group agrees on it. Sorting inside each bucket gives the required output order. Time is O(E log E) dominated by the sorting, space O(E).
def merge_accounts(accounts):
parent, owner = {}, {}
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path halving
x = parent[x]
return x
for name, *emails in accounts:
for e in emails:
parent.setdefault(e, e)
owner[e] = name # any email carries the name
for e in emails[1:]:
parent[find(e)] = find(emails[0]) # one account, one set
groups = {}
for e in parent:
groups.setdefault(find(e), []).append(e)
return sorted([owner[root]] + sorted(es) for root, es in groups.items())
print(merge_accounts([["Jo", "a@x", "b@x"], ["Jo", "b@x", "c@x"], ["Kim", "d@x"]]))
# -> [['Jo', 'a@x', 'b@x', 'c@x'], ['Kim', 'd@x']]
print(merge_accounts([["Jo", "a@x"], ["Jo", "z@x"]])) # -> [['Jo', 'a@x'], ['Jo', 'z@x']]Stuck on the idea rather than the code? Union by Rank or Size covers it.