How to Solve Accounts Merge

This problem is about identifying accounts that share common emails and merging them. Using array scanning and hash lookup, you can build a graph of emails and find connected components. Sorting emails after merging ensures consistent output while efficiently handling multiple accounts per user.

Problem Statement

Given a list of accounts where each account contains a user's name followed by their email addresses, merge all accounts that belong to the same person. Accounts belong to the same person if they share at least one email, even if names differ, and each account has at least one email.

Return the merged accounts with the user's name first, followed by all their emails in sorted order. The order of accounts in the final list does not matter, but each user's emails must be sorted lexicographically, and duplicate emails must be removed.

Examples

Example 1

Input: accounts = [["John","johnsmith@mail.com","john_newyork@mail.com"],["John","johnsmith@mail.com","john00@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]

Output: [["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]

The first and second John's are the same person as they have the common email "johnsmith@mail.com". The third John and Mary are different people as none of their email addresses are used by other accounts. We could return these lists in any order, for example the answer [['Mary', 'mary@mail.com'], ['John', 'johnnybravo@mail.com'], ['John', 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com']] would still be accepted.

Example 2

Input: 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"]]

Output: [["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"]]

Example details omitted.

Constraints

• 1 <= accounts.length <= 1000
• 2 <= accounts[i].length <= 10
• 1 <= accounts[i][j].length <= 30
• accounts[i][0] consists of English letters.
• accounts[i][j] (for j > 0) is a valid email.

Solution Approach

Graph Construction via Hash Mapping

Scan each account and map each email to a unique node. For each account, link all emails with edges using a hash table for fast lookups. This transforms the problem into finding connected components of the email graph.

Connected Components Enumeration

Perform DFS or BFS starting from each unvisited email node to collect all emails connected to that node. Each traversal identifies a single person's merged account, ensuring no emails are counted twice and all shared accounts are merged correctly.

Sorting and Building the Result

After collecting all emails for each connected component, sort the emails lexicographically and prepend the associated user's name. Aggregate all merged accounts into a result list and return it as the final answer.

Complexity Analysis

Time complexity is O(NK log NK) where N is the number of accounts and K is the maximum emails per account due to sorting. Space complexity is O(NK) for storing the graph and visited flags for emails.

What Interviewers Usually Probe

• Building a graph of emails is expected, indicating awareness of array scanning plus hash lookup.
• Mentioning DFS, BFS, or Union-Find shows proper connected component handling.
• Sorting emails before returning results indicates attention to problem-specific output requirements.

Common Pitfalls or Variants

Common pitfalls

• Assuming same name implies same person, which fails when names repeat but emails differ.
• Forgetting to remove duplicate emails when merging accounts.
• Not linking all emails in the same account, leading to disconnected components and incomplete merges.

Follow-up variants

• Accounts Merge II with phone numbers instead of emails.
• Accounts Merge with dynamic account additions in real-time streaming.
• Accounts Merge with additional constraints on maximum account size or email count.

How GhostInterview Helps

• GhostInterview highlights connected-component patterns using array scanning plus hash lookup, showing exactly how to link emails.
• It points out common pitfalls like duplicate emails and repeated names to avoid incorrect merges.
• Provides a structured approach to sort and format results efficiently while maintaining linear traversal logic.

Topic Pages

• Array
• Hash Table
• String
• Depth-First Search
• Breadth-First Search
• Union Find
• Sorting

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the core pattern in Accounts Merge?

The problem follows an array scanning plus hash lookup pattern to build a graph and find connected components of emails.

Can two accounts with the same name be different people?

Yes, accounts with the same name must be checked via shared emails; same names do not guarantee the same person.

Which traversal methods are suitable for merging accounts?

DFS, BFS, or Union-Find can be used to explore connected components of the email graph for merging accounts.

Do merged emails need sorting?

Yes, emails for each merged account must be sorted lexicographically to meet the output requirements.

What is the time and space complexity for Accounts Merge?

Time complexity is O(NK log NK) due to sorting, and space complexity is O(NK) to store the email graph and visited states.