Accounts Merge

Problem

You are given a list of accounts. Each account is [name, email1, email2, ...]. Two accounts belong to the same person if they share at least one email. Merge all accounts belonging to the same person and return the merged list with emails sorted alphabetically.

accounts = [
  ["John","a@j.com","b@j.com"],
  ["John","b@j.com","c@j.com"],
  ["Mary","d@m.com"]
]
→ [["John","a@j.com","b@j.com","c@j.com"],["Mary","d@m.com"]]

Solution

Approach - Dict-keyed Union-Find over email addresses, then group by root.

The shared entity is the email, not the account index - two accounts belong to the same person exactly when they share an email. So we run Union-Find on email strings. parent is a dict (an email is its own parent on first sight) and find is the usual path-compressing recursion, identical to integer Union-Find but keyed by string. In the first pass over each account, we anchor on account[1] (the first email) and union every other email in that row to it - that links all of one account's emails into a single component, and shared emails transitively merge whole accounts. We also record email_to_name[email] = name so we can recover the display name later from any email in the group.

The second pass walks every email, computes its root with find, and buckets emails into groups[root] as a set - the set deduplicates an email that appeared in multiple accounts. Finally each group becomes [name] + sorted(emails), where the name comes from email_to_name[root] and emails are sorted to meet the lexicographic requirement.

Trace the two Johns sharing b@j.com: unioning within each account plus the shared b@j.com collapses all of a,b,c@j.com into one root, yielding one John with three sorted emails.

Edge cases - A single-email account runs zero union iterations but still lands in parent and surfaces in grouping. Same name with no shared email stays separate - only emails merge, never names.

Complexity - O(N * K * alpha) for the unions plus O(N * K * log(N * K)) for sorting, where N accounts have K emails each. O(N * K) space for the parent dict, name map, and groups.