Accounts Merge (LeetCode 721)
You're given accounts, a list where each entry is [name, email1, email2, ...] -- one person's name followed by every email on that account.
Merge accounts that belong to the same real person: two accounts are the same person whenever they share at least one email, even transitively through a chain of shared emails. Two accounts with the same name are NOT automatically the same person -- only a shared email proves that -- and one person may hold several accounts, all under their one name.
Return the merged accounts, each as [name, ...emails sorted ascending]; the accounts themselves can come back in any order.
Worked Examples
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"]]accounts = [["Gabe","Gabe0@m.co","Gabe3@m.co","Gabe1@m.co"],["Kevin","Kevin3@m.co","Kevin5@m.co","Kevin0@m.co"],["Ethan","Ethan5@m.co","Ethan4@m.co","Ethan0@m.co"],["Hanzo","Hanzo3@m.co","Hanzo1@m.co","Hanzo0@m.co"],["Fern","Fern5@m.co","Fern1@m.co","Fern0@m.co"]][["Ethan","Ethan0@m.co","Ethan4@m.co","Ethan5@m.co"],["Gabe","Gabe0@m.co","Gabe1@m.co","Gabe3@m.co"],["Hanzo","Hanzo0@m.co","Hanzo1@m.co","Hanzo3@m.co"],["Kevin","Kevin0@m.co","Kevin3@m.co","Kevin5@m.co"],["Fern","Fern0@m.co","Fern1@m.co","Fern5@m.co"]]⚖️Formal Constraints & Bounds
1 <= accounts.length <= 10002 <= accounts[i].length <= 101 <= accounts[i][j].length <= 30accounts[i][0]consists of English letters.accounts[i][j] (for j > 0)is a valid email.
Core Insight
DSU transitivity clusters overlapping identity records without explicit adjacency list graphs.
Real-World Scenario & Production Applications
Identity resolution in customer data platforms (CDP), fraud detection entity resolution.
Step-by-Step Execution Trace Table
| Account | Emails | Union Action | Canonical Root |
|---|---|---|---|
| John 1 | 'johnsmith', 'john_newyork' | union('john_newyork', 'johnsmith') | 'johnsmith' |
| John 2 | 'johnsmith', 'john00' | union('john00', 'johnsmith') | 'johnsmith' |
| Mary | 'mary' | self root | 'mary' |
| 1 | Map email -> parent and email -> owner |
| 2 | Union all emails in each account to account's first email |
| 3 | Group by find(email), sort emails, return [owner] + sorted_emails |
Conceptual Narrative
Multiple user accounts sharing a single email address belong to the same person. Treating emails as graph nodes and unifying secondary emails to the primary email clusters overlapping accounts in O(N log N) time.
🧭 Conceptual Foundation & Pattern Intuition
In Accounts Merge (LC 721), each account has a name and a list of email addresses. Two accounts belong to the same person if they share at least one common email. Notice that email overlap is transitive: if Account 1 shares an email with Account 2, and Account 2 shares an email with Account 3, all three accounts belong to the same human, even if Account 1 and Account 3 have no emails in common. This transitivity is the signature of Connected Components in an Equivalence Graph:
- Each unique email address is a node in our DSU.
- For each account with emails , we union to .
- We record the owner's name for the canonical root email.
- Finally, we group all emails by their canonical root
find(email), sort each email group lexicographically, and prepend the owner's name.
🕵️ The Analogy: Unmasking Pseudonyms by Shared Contact Info
Imagine an investigator analyzing fraudulent bank accounts. Account A uses emails "john@gmail.com" and "john_work@corp.com". Account B uses "john_work@corp.com" and "john_vpn@anon.to". Even though Account A and Account B used different account IDs, the shared work email links them into a single identity ring. By pinning all emails to the first email seen on each application form, the investigator groups all aliases into unified dossiers.
🔑 Why It Works
The elegance of DSU is that we never build or traverse an explicit adjacency graph with BFS/DFS; the Disjoint Set automatically groups all transitively connected emails under their shared canonical parent.
Matching on account names: Two distinct people can share the same name (e.g. two different 'John's). Never union accounts solely by name; union strictly by shared email addresses.
All-pairs email union : Unioning every email with every other email in an account takes quadratic time; unioning each email with the first email takes linear time.
Missing sorted output requirement: Forgetting to sort email lists alphabetically (
sorted(emails)) before returning violates LC 721 output specification.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Identity resolution / merging records that share overlapping identifiers.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: emails belonging to the same person share a canonical DSU root.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I map each email to its owner name and initialize its DSU parent. For each account, I union all subsequent emails to the account's first email
union(first_email, email). I group all emails by their canonical rootfind(email)and return each group with the owner name and sorted emails. Runs in O(N · K log(NK)) time and O(N · K) space."
Complexity & Mathematical Proof
O(A · K · alpha(N) + A · K log(A · K))
Look at the execution steps: Let A be number of accounts and K be max emails per account. Maps emails to account IDs and unions shared emails in O(A · K · alpha(N)). Sorting emails per component takes O(A · K log(A · K)). Total O(A · K log(A · K)).
O(A · K) Auxiliary
Look at memory allocations: parent, rank and owner hold one entry per distinct email, and groups lists every email once: O(A · K) for A accounts of up to K emails. find calls itself once per level of a tree, and union by rank keeps every tree at most log2(A · K) + 1 levels tall, so the call stack is O(log(A · K)).
T(A, K) = O(A · K · α(N)) + O(A · K log(A · K))
Derivation Progression
union(first_email, e)
Links all emails in same account in DSU in O(A · K · alpha(N)).
groups[find(e)].append(e)
Groups emails by representative root in O(A · K).
∑ |Gi| log |Gi| ≤ O(A · K log(A · K))
Sorts emails per merged account.
Variable Definitions
Total number of account objects
Maximum number of email addresses per account
Inverse Ackermann function (α ≤ 4)
Memory Architecture & Bounds
O(log(A · K)) Recursive find, union by rank
O(A · K) DSU parent map and email lookup dictionaries
O(A · K) Merged account list
Boundary Best / Worst Cases
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "merge accounts if they share an email", "person can have multiple accounts with same name". Multi-identity equivalence clustering: union accounts that share common identifiers. A Senior SWE maps each email to an account index, and unions account IDs directly in a DSU.
accounts, each with emails. Total emails . Budget sorting.
Accounts sharing the same name but with completely disjoint emails represent different people and MUST remain separate. Emails in each merged account must be sorted lexicographically.
Accounts Merge (LeetCode 721)
You're given accounts, a list where each entry is [name, email1, email2, ...] -- one person's name followed by every email on that account.
Merge accounts that belong to the same real person: two accounts are the same person whenever they share at least one email, even transitively through a chain of shared emails. Two accounts with the same name are NOT automatically the same person -- only a shared email proves that -- and one person may hold several accounts, all under their one name.
Return the merged accounts, each as [name, ...emails sorted ascending]; the accounts themselves can come back in any order.
Worked Examples
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"]]accounts = [["Gabe","Gabe0@m.co","Gabe3@m.co","Gabe1@m.co"],["Kevin","Kevin3@m.co","Kevin5@m.co","Kevin0@m.co"],["Ethan","Ethan5@m.co","Ethan4@m.co","Ethan0@m.co"],["Hanzo","Hanzo3@m.co","Hanzo1@m.co","Hanzo0@m.co"],["Fern","Fern5@m.co","Fern1@m.co","Fern0@m.co"]][["Ethan","Ethan0@m.co","Ethan4@m.co","Ethan5@m.co"],["Gabe","Gabe0@m.co","Gabe1@m.co","Gabe3@m.co"],["Hanzo","Hanzo0@m.co","Hanzo1@m.co","Hanzo3@m.co"],["Kevin","Kevin0@m.co","Kevin3@m.co","Kevin5@m.co"],["Fern","Fern0@m.co","Fern1@m.co","Fern5@m.co"]]⚖️Formal Constraints & Bounds
1 <= accounts.length <= 10002 <= accounts[i].length <= 101 <= accounts[i][j].length <= 30accounts[i][0]consists of English letters.accounts[i][j] (for j > 0)is a valid email.
Core Insight
DSU transitivity clusters overlapping identity records without explicit adjacency list graphs.
Real-World Scenario & Production Applications
Identity resolution in customer data platforms (CDP), fraud detection entity resolution.
Step-by-Step Execution Trace Table
| Account | Emails | Union Action | Canonical Root |
|---|---|---|---|
| John 1 | 'johnsmith', 'john_newyork' | union('john_newyork', 'johnsmith') | 'johnsmith' |
| John 2 | 'johnsmith', 'john00' | union('john00', 'johnsmith') | 'johnsmith' |
| Mary | 'mary' | self root | 'mary' |
| 1 | Map email -> parent and email -> owner |
| 2 | Union all emails in each account to account's first email |
| 3 | Group by find(email), sort emails, return [owner] + sorted_emails |
Conceptual Narrative
Multiple user accounts sharing a single email address belong to the same person. Treating emails as graph nodes and unifying secondary emails to the primary email clusters overlapping accounts in O(N log N) time.
🧭 Conceptual Foundation & Pattern Intuition
In Accounts Merge (LC 721), each account has a name and a list of email addresses. Two accounts belong to the same person if they share at least one common email. Notice that email overlap is transitive: if Account 1 shares an email with Account 2, and Account 2 shares an email with Account 3, all three accounts belong to the same human, even if Account 1 and Account 3 have no emails in common. This transitivity is the signature of Connected Components in an Equivalence Graph:
- Each unique email address is a node in our DSU.
- For each account with emails , we union to .
- We record the owner's name for the canonical root email.
- Finally, we group all emails by their canonical root
find(email), sort each email group lexicographically, and prepend the owner's name.
🕵️ The Analogy: Unmasking Pseudonyms by Shared Contact Info
Imagine an investigator analyzing fraudulent bank accounts. Account A uses emails "john@gmail.com" and "john_work@corp.com". Account B uses "john_work@corp.com" and "john_vpn@anon.to". Even though Account A and Account B used different account IDs, the shared work email links them into a single identity ring. By pinning all emails to the first email seen on each application form, the investigator groups all aliases into unified dossiers.
🔑 Why It Works
The elegance of DSU is that we never build or traverse an explicit adjacency graph with BFS/DFS; the Disjoint Set automatically groups all transitively connected emails under their shared canonical parent.
Matching on account names: Two distinct people can share the same name (e.g. two different 'John's). Never union accounts solely by name; union strictly by shared email addresses.
All-pairs email union : Unioning every email with every other email in an account takes quadratic time; unioning each email with the first email takes linear time.
Missing sorted output requirement: Forgetting to sort email lists alphabetically (
sorted(emails)) before returning violates LC 721 output specification.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Identity resolution / merging records that share overlapping identifiers.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: emails belonging to the same person share a canonical DSU root.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I map each email to its owner name and initialize its DSU parent. For each account, I union all subsequent emails to the account's first email
union(first_email, email). I group all emails by their canonical rootfind(email)and return each group with the owner name and sorted emails. Runs in O(N · K log(NK)) time and O(N · K) space."
Complexity & Mathematical Proof
O(A · K · alpha(N) + A · K log(A · K))
Look at the execution steps: Let A be number of accounts and K be max emails per account. Maps emails to account IDs and unions shared emails in O(A · K · alpha(N)). Sorting emails per component takes O(A · K log(A · K)). Total O(A · K log(A · K)).
O(A · K) Auxiliary
Look at memory allocations: parent, rank and owner hold one entry per distinct email, and groups lists every email once: O(A · K) for A accounts of up to K emails. find calls itself once per level of a tree, and union by rank keeps every tree at most log2(A · K) + 1 levels tall, so the call stack is O(log(A · K)).
T(A, K) = O(A · K · α(N)) + O(A · K log(A · K))
Derivation Progression
union(first_email, e)
Links all emails in same account in DSU in O(A · K · alpha(N)).
groups[find(e)].append(e)
Groups emails by representative root in O(A · K).
∑ |Gi| log |Gi| ≤ O(A · K log(A · K))
Sorts emails per merged account.
Variable Definitions
Total number of account objects
Maximum number of email addresses per account
Inverse Ackermann function (α ≤ 4)
Memory Architecture & Bounds
O(log(A · K)) Recursive find, union by rank
O(A · K) DSU parent map and email lookup dictionaries
O(A · K) Merged account list
Boundary Best / Worst Cases
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "merge accounts if they share an email", "person can have multiple accounts with same name". Multi-identity equivalence clustering: union accounts that share common identifiers. A Senior SWE maps each email to an account index, and unions account IDs directly in a DSU.
accounts, each with emails. Total emails . Budget sorting.
Accounts sharing the same name but with completely disjoint emails represent different people and MUST remain separate. Emails in each merged account must be sorted lexicographically.