Accounts Merge

Difficulty: Medium Source: NeetCode

Problem

Given a list of accounts where each element accounts[i] is a list of strings, where accounts[i][0] is a name, and the rest of the elements are emails representing emails of the account.

Now, we would like to merge these accounts. Two accounts definitely belong to the same person if there is some common email to both accounts. Note that even if two accounts have the same name, they may belong to different people as people could have the same name. A person can have any number of accounts initially, but all of their accounts definitely have the same name.

After merging the accounts, return the accounts in any order. Each account should be in the format [name, email1, email2, ...] where emails are sorted in alphabetical order.

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

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

Prerequisites

Before attempting this problem, you should be comfortable with:

• Union-Find — merging connected email groups efficiently
• DFS on a graph — treating emails as nodes connected by shared accounts
• Hash Maps — mapping emails to accounts or Union-Find parents

1. DFS (Graph of Emails)

Intuition

Build a graph where emails are nodes, and two emails are connected by an edge if they appear in the same account. Then, each connected component in this graph represents one person. For each component, collect all emails, sort them, and prepend the account name.

Algorithm

1. Build an adjacency list: for each account, connect all its emails to the first email of that account (acts as a hub). Also track email_to_name.
2. Run DFS from each unvisited email, collecting the full connected component.
3. Sort each component’s emails and prepend the name.

Solution

from collections import defaultdict

def accountsMerge(accounts: list[list[str]]) -> list[list[str]]:
    graph = defaultdict(set)
    email_to_name = {}

    for account in accounts:
        name = account[0]
        first_email = account[1]
        for email in account[1:]:
            email_to_name[email] = name
            graph[first_email].add(email)
            graph[email].add(first_email)

    visited = set()
    result = []

    def dfs(email, component):
        visited.add(email)
        component.append(email)
        for neighbor in graph[email]:
            if neighbor not in visited:
                dfs(neighbor, component)

    for email in email_to_name:
        if email not in visited:
            component = []
            dfs(email, component)
            result.append([email_to_name[email]] + sorted(component))

    return result


accounts = [["John","johnsmith@mail.com","john_newyork@mail.com","john00@mail.com"],
            ["John","johnnybravo@mail.com"],
            ["John","johnsmith@mail.com","john_newyork@mail.com"],
            ["Mary","mary@mail.com"]]
for row in sorted(accountsMerge(accounts)):
    print(row)

Complexity

• Time: O(N * K * log(N * K)) where N = accounts, K = avg emails per account (sorting dominates)
• Space: O(N * K) for graph and visited set

2. Union-Find

Intuition

Use Union-Find on email addresses. For each account, union all emails with the first email (or with each other). After processing all accounts, group emails by their root (component representative). Sort each group and prepend the account name.

Algorithm

1. Map each unique email to an integer index.
2. Initialize Union-Find on indices.
3. For each account, union all email indices with the first email’s index.
4. Group email indices by their find root.
5. For each group, sort emails and prepend the name.

Solution

from collections import defaultdict

def accountsMerge(accounts: list[list[str]]) -> list[list[str]]:
    parent = {}
    email_to_name = {}

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(x, y):
        parent[find(x)] = find(y)

    # Initialize Union-Find for all emails
    for account in accounts:
        name = account[0]
        for email in account[1:]:
            if email not in parent:
                parent[email] = email
            email_to_name[email] = name

    # Union emails within the same account
    for account in accounts:
        first = account[1]
        for email in account[2:]:
            union(first, email)

    # Group emails by root
    components = defaultdict(list)
    for email in parent:
        components[find(email)].append(email)

    result = []
    for root, emails in components.items():
        result.append([email_to_name[root]] + sorted(emails))

    return result


accounts = [["John","johnsmith@mail.com","john_newyork@mail.com","john00@mail.com"],
            ["John","johnnybravo@mail.com"],
            ["John","johnsmith@mail.com","john_newyork@mail.com"],
            ["Mary","mary@mail.com"]]
for row in sorted(accountsMerge(accounts)):
    print(row)

Complexity

• Time: O(N * K * α(N * K) + N * K * log(N * K)) — nearly O(N * K * log(N * K)) due to sorting
• Space: O(N * K) for Union-Find and grouping

Common Pitfalls

Same name ≠ same person. Two accounts with the same name are only merged if they share an email. Don’t use the name as the merge key.

Email appears in multiple accounts. An email can link two accounts that otherwise have no other email in common. The graph/Union-Find approach handles this naturally since the shared email creates the connection.

Sorting emails after merging. The problem requires emails sorted alphabetically within each account. Don’t forget to sort after grouping.