Accounts Merge
Last Updated: April 5, 2026
Understanding the Problem
At first, this problem looks like simple string matching, but there is a subtlety that makes it more interesting. Two accounts belong to the same person if they share even one email. But the merging is transitive: if account A shares an email with account B, and account B shares an email with account C, then all three belong to the same person, even if A and C share nothing directly.
This transitive merging is the key challenge. You can't just do pairwise comparisons and call it a day. You need to find connected components, where emails are nodes and accounts create edges between them. Once you identify which emails belong together, you group them, sort them, and attach the right name.
Key Constraints:
1 <= accounts.length <= 1000-> With up to 1000 accounts and 10 emails each, that's at most 10,000 emails. Even O(n^2) on accounts is fine, but graph-based techniques give cleaner solutions.2 <= accounts[i].length <= 10-> Each account has at least one email and at most 9 emails. Email lists are small.1 <= accounts[i][j].length <= 30-> Email strings are short, so hashing and comparison are cheap.
Approach 1: DFS on Email Graph
Intuition
If we think of each email as a node, and draw an edge between two emails whenever they appear in the same account, then finding merged accounts is the same as finding connected components in this graph.
Within a single account like ["John", "a@mail.com", "b@mail.com", "c@mail.com"], we know a, b, and c all belong together. We don't need to connect every pair though. Connecting each email to the first email in the account is enough: a-b, a-c. This forms a star graph that keeps all three in the same component.
Once the graph is built, we run DFS from each unvisited email, collecting all reachable emails into one group. Each group becomes one merged account.
Algorithm
- Build an adjacency list: for each account, connect every email to the first email in that account (bidirectional edges).
- Also maintain a map from each email to its account name.
- Initialize a visited set.
- For each unvisited email, run DFS to collect all emails in that connected component.
- Sort the collected emails, prepend the account name, and add to the result.
Example Walkthrough
Code
- Time Complexity: O(NK log NK). N is the number of accounts and K is the max emails per account. Building the graph is O(NK). DFS visits each email once. Sorting dominates at O(NK log NK) in the worst case.
- Space Complexity: O(NK). The adjacency list, visited set, and email-to-name map each store up to NK entries.
This approach works but requires building an explicit adjacency list and traversing it. What if we could group emails incrementally without constructing a full graph?
Approach 2: Union Find
Intuition
Union Find (also called Disjoint Set Union) is purpose-built for this exact scenario: we have a collection of elements, and we need to merge groups together whenever we discover a connection. Instead of building an adjacency list and traversing it, we can process each account by simply unioning all its emails together.
For each account, take the first email as the representative. Union every other email in that account with the first email. After processing all accounts, emails that belong to the same person will share the same root in the Union Find structure. The beauty is that transitivity is handled automatically.
Union Find maintains a forest of trees where each tree represents a connected component. The find operation with path compression flattens the tree structure, making subsequent lookups nearly O(1). The union operation with rank-based merging keeps trees balanced.
When we union all emails in the same account, we're saying "these emails belong to the same person." Because Union Find handles transitivity through the tree structure, if email B connects accounts 1 and 2, all emails from both accounts naturally end up under the same root. No explicit graph traversal needed.
Algorithm
- Initialize a Union Find structure where each email is its own parent.
- For each account, union all emails in that account with the first email.
- After all unions, find the root of each email and group emails by their root.
- Sort each group, prepend the account name, and add to the result.
Example Walkthrough
Code
- Time Complexity: O(NK alpha(NK) + NK log NK). Processing accounts with Union Find takes O(NK alpha(NK)) where alpha is the inverse Ackermann function (effectively constant). Sorting the grouped emails takes O(NK log NK) and dominates.
- Space Complexity: O(NK). The parent map, rank map, and email-to-name map each store up to NK entries.