Accounts Merge
Problem Statement
Given a list of accounts, each account is shaped as [name, email1, email2, ...]. Two accounts belong to the same person if they share at least one email address. The same person may appear in multiple accounts, and two different people may have the same name.
Merge all accounts that belong to the same person. Each merged account should contain the person's name followed by that person's unique emails in lexicographic order. The merged accounts themselves may be returned in any order.
Input
A list accounts where the first value in each row is a name and every later value is an email address owned by that account.
Output
A list of merged accounts. Each account starts with the owner name, followed by the sorted unique emails in that connected email group.
Constraints
- •
1 <= accounts.length <= 1000 - •
2 <= accounts[i].length <= 10 - •
1 <= name.length, email.length <= 30 - •
accounts[i][0] is a name and the remaining values are emails - •
Each email consists of lowercase English letters, digits, dots, plus signs, or at signs
Examples
Example 1
accounts = [ ["John","johnsmith@mail.com","john_newyork@mail.com"], ["John","johnsmith@mail.com","john00@mail.com"], ["Mary","mary@mail.com"], ["John","johnnybravo@mail.com"] ]
[
["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],
["Mary","mary@mail.com"],
["John","johnnybravo@mail.com"]
]Example 2
accounts = [ ["Alex","a@mail.com","b@mail.com"], ["Alex","c@mail.com","b@mail.com"], ["Alex","d@mail.com","c@mail.com"] ]
[["Alex","a@mail.com","b@mail.com","c@mail.com","d@mail.com"]]Learning Objectives
- Model emails as graph nodes and shared accounts as edges that connect those emails.
- Use Union-Find to merge connected components without building an explicit adjacency list.
- Separate identity discovery from output formatting: first group by root, then sort emails and prepend the name.
Intuition
The important mental shift is that accounts are not the real components; emails are. If two emails appear in the same account, they must belong to the same person, so we can connect them. If an email later appears in another account, that account's emails are pulled into the same component too. This is exactly the transitive merging behavior Union-Find is designed for.
Treat every unique email as a node. For each account, union the first email with every other email in that row. After all unions, every root represents one real person. The final pass is just bookkeeping: collect all emails under their root, sort each group, and use any email in the group to look up the owner's name.
Why not merge account rows directly? Because a person can be spread across several rows, and the bridge might be any email, not necessarily the first row you saw. Union-Find lets every shared email collapse the right components no matter what order the rows arrive in.
Common mistakes
- ×Unioning account indices but then losing the unique email set; unioning emails directly makes grouping and sorting cleaner.
- ×Forgetting transitivity: if account A shares with B and B shares with C, all three must merge even if A and C share no direct email.
- ×Returning emails in discovery order instead of lexicographic order.
- ×Using the account name as an identity key. Different people may share the same name; emails determine identity.
- ×Looking up the output name from an arbitrary account index after grouping by email root. Store email to name while scanning.
Algorithm Explanation
- Scan every account and assign each unique email a compact integer id. Also store email → name.
- Create a Union-Find with one node per unique email.
- For each account, union the id of its first email with the id of every other email in the same account. This makes all emails in that account part of one component.
- Iterate over every unique email, find its root, and append the email to the list for that root.
- Sort each root's email list, create an output row with the owner name followed by the sorted emails, and return all rows.
Solutions
Solution: Union-Find over emails
Use this when the problem asks for transitive merging of identities. It is more direct than graph traversal because every shared email immediately collapses two sets, and the final grouping is by root.
Map each unique email to an id, union all emails that appear in the same account, then group emails by their representative root. Sorting is done only after the components are known.
Step-by-step
- Build emailToId and emailToName in one scan.
- In a second scan, take the first email of each account as the anchor and union it with every later email in that account.
- Create rootToEmails by finding each email's compressed root.
- For every component, sort the emails, prepend emailToName from any email in that component, and add the row to the answer.
O(E · α(U) + U log U)
O(U)
E is the number of email mentions and U is the number of unique emails. Sorting all groups is bounded by sorting U emails overall.
Java implementation
Dry Run
Sample input
accounts = [[John, johnsmith@mail.com, john_newyork@mail.com], [John, johnsmith@mail.com, john00@mail.com], [Mary, mary@mail.com]]
| Step | Operation | Components | Output effect |
|---|---|---|---|
| 1 | Assign ids to four unique emails | each email is alone | No output yet |
| 2 | Union johnsmith with john_newyork | {johnsmith, john_newyork} | First John component formed |
| 3 | Union johnsmith with john00 | {johnsmith, john_newyork, john00} | Second John row joins same root |
| 4 | Mary has one email | {mary} remains separate | Mary will be its own row |
| 5 | Group by root and sort | John group plus Mary group | Return sorted emails under each name |
The shared email johnsmith@mail.com is the bridge between the two John rows. Once both rows point into the same DSU root, grouping by root naturally produces one sorted John account and one Mary account.
Interview Tips
Lead with the graph model: emails are nodes, and co-occurrence in an account is an edge. Then immediately say Union-Find is ideal because the problem asks for connected components, not paths. Be explicit that names are labels, not keys. When you describe output construction, mention sorting each component and using any email in the component to recover the name.
Likely follow-ups
- What changes if accounts arrive in a stream and you must merge online? Keep the email id map and Union-Find alive across inserts.
- What if an email can be reassigned to a different person later? DSU does not support efficient splits; you would need a different data model.
- How would you make output deterministic across runs? Sort the final list of merged accounts by name and then first email.
- Can you solve it with DFS? Yes, build an email adjacency list from each account and traverse components.
Similar Problems
Key Takeaways
- Identity merge problems usually hide connected components over identifiers.
- Union all evidence first; format and sort output only after components are stable.
- Names are metadata here. Emails define connectivity.
- Path compression plus union by size makes repeated merges effectively constant time.