Each entry of accounts is a list whose first element is a person's name and the rest are email addresses. Two accounts belong to the same person if they share at least one email (people with the same name may still be different people). Merge the accounts and return them as [name, emails...] with the emails in sorted order. The accounts themselves may be returned in any order.
johnsmith@mail.com, so they merge. The last John shares nothing, so he stays separate.- 1 <= accounts.length <= 1000
- 2 <= accounts[i].length <= 10
- 1 <= accounts[i][j].length <= 30
- Names are English letters, emails are valid addresses
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force repeatedly compares every pair of accounts and merges any two that share an email until nothing changes, which is O(n^2) or worse per pass. The real structure is a graph: emails are nodes, and an account links all its emails. Every merged account is a connected component. Union Find builds components in near linear time: union each email of an account with that account's first email, then gather emails by their root, sort them, and put the owner's name in front.
Algorithm
- Map each new email to an id and remember the name of the account it first appeared in.
- For every account, union the id of each email with the id of its first email.
- Group all emails by the root of their id.
- For each group, sort the emails and prepend the name.
O(N log N) where N is the total number of emails (sorting dominates)Space: O(N)class Solution: def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]: parent = {} owner = {}ย def find(x): while parent[x] != x: parent[x] = parent[parent[x]] # path halving x = parent[x] return xย for acc in accounts: name, first = acc[0], acc[1] for email in acc[1:]: if email not in parent: parent[email] = email owner[email] = name for email in acc[1:]: ra, rb = find(email), find(first) if ra != rb: parent[ra] = rb # link to the first email of this accountย groups = defaultdict(list) for email in parent: groups[find(email)].append(email) return [[owner[root]] + sorted(emails) for root, emails in groups.items()]