Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Accounts Merge
• Topics: Array, Hash Table, String, Depth-First Search, Breadth-First Search, Union-Find, Sorting

Problem gist

Each account is a list where the first value is a person’s name and the remaining values are email addresses. Two accounts belong to the same real person if they share at least one email address. The task is to merge every connected set of accounts and return one account per person, with the person’s name followed by that person’s emails in sorted order.

The important detail is that the name alone does not identify a person. Two different people may have the same name. Shared email addresses are the reliable signal. So the problem is really asking for connected components among emails.

Core idea

Treat every email as a node. Whenever two emails appear in the same account, connect them because they must belong to the same person. After all accounts have been processed, every connected component is one merged account.

Union-Find is a natural fit for this because it maintains groups under repeated “these two items are connected” operations:

1. Give every email its own group the first time it appears.
2. For each account, union every email in that account with the account’s first email.
3. After all unions, group emails by their final representative.
4. Sort each group of emails and prepend the owner’s name.

This avoids repeatedly traversing a graph while the input is being read. It also keeps the implementation focused on the one relationship that matters: emails appearing together in an account.

Deriving the algorithm

For an account like ["John", "a@mail.com", "b@mail.com", "c@mail.com"], it is enough to union a with b and a with c. Once those unions are done, all three emails are in the same component. There is no need to union every pair of emails inside the account.

While reading the accounts, also store email_to_name[email] = name. The problem guarantees that emails in the same merged account belong to the same person, so any email in a component can recover the correct name for the final output.

After processing all accounts, walk through every known email, find its Union-Find root, and append it to a list for that root. Each root bucket is now one merged person. Sorting the emails inside each bucket satisfies the output requirement.

Python solution

from collections import defaultdict
from typing import DefaultDict, Dict, List


EmailList = List[str]
Account = List[str]
EmailGroups = DefaultDict[str, EmailList]


class UnionFind:
    def __init__(self) -> None:
        self.parent: Dict[str, str] = {}
        self.group_size: Dict[str, int] = {}

    def add(self, item: str) -> None:
        if item not in self.parent:
            self.parent[item] = item
            self.group_size[item] = 1

    def find(self, item: str) -> str:
        root = item
        while root != self.parent[root]:
            root = self.parent[root]

        # Path compression keeps future lookups nearly constant-time.
        while item != root:
            next_parent = self.parent[item]
            self.parent[item] = root
            item = next_parent

        return root

    def union(self, first: str, second: str) -> None:
        self.add(first)
        self.add(second)

        first_root = self.find(first)
        second_root = self.find(second)
        if first_root == second_root:
            return

        if self.group_size[first_root] < self.group_size[second_root]:
            first_root, second_root = second_root, first_root

        self.parent[second_root] = first_root
        self.group_size[first_root] += self.group_size[second_root]


class Solution:
    def accountsMerge(self, accounts: List[Account]) -> List[Account]:
        union_find = UnionFind()
        email_to_name: Dict[str, str] = {}

        for account in accounts:
            if len(account) < 2:
                continue

            name = account[0]
            first_email = account[1]
            union_find.add(first_email)
            email_to_name[first_email] = name

            for email in account[2:]:
                email_to_name[email] = name
                union_find.union(first_email, email)

        emails_by_root: EmailGroups = defaultdict(list)
        for email in email_to_name:
            root = union_find.find(email)
            emails_by_root[root].append(email)

        merged_accounts: List[Account] = []
        for root_email, emails in emails_by_root.items():
            name = email_to_name[root_email]
            merged_accounts.append([name] + sorted(emails))

        # LeetCode accepts any account order, but deterministic output is nicer.
        merged_accounts.sort(key=lambda account: (account[0], account[1:]))
        return merged_accounts

Complexity

Let E be the total number of email entries across all accounts, and let U be the number of unique email addresses.

The Union-Find operations take O(E * alpha(U)) time, where alpha is the inverse Ackermann function and is effectively constant for practical input sizes. Sorting the final email groups costs O(U log U) in the worst case if one person owns every email. The total time is therefore O(E * alpha(U) + U log U).

The extra space is O(U) for the Union-Find parent map, group sizes, email-to-name map, and final grouping map.

Interview follow-ups

Could this be solved with DFS or BFS instead of Union-Find?

Yes. Build an undirected graph where every email is a node, and emails in the same account are connected by edges. Then run DFS or BFS from each unvisited email to collect one connected component at a time.

The graph approach works for the same reason Union-Find works: merged accounts are connected components. Its time complexity is O(E + U log U) if each account connects its first email to the rest and each output group is sorted. The tradeoff is that it stores explicit adjacency lists, while Union-Find stores only parent links and group sizes.

Why union every email with the first email instead of every pair?

All emails in one account belong to the same person, so they only need to end up in the same connected component. Unioning each email with the first email creates a star-shaped connection that joins the whole account.

Unioning every pair would also be correct, but it does unnecessary work. If an account has k emails, the star method performs k - 1 unions, while pairwise union performs O(k^2) unions. Both produce the same component, but the star method scales better.

What if two different people have the same name?

The algorithm still works because it never merges by name. It only merges by shared email. If two accounts are both named "John" but have no email overlap through any chain of accounts, they remain separate components and produce separate output accounts.

This is exactly why the email graph is the right model. The name is metadata attached to a component after connectivity has been determined, not the key used to decide connectivity.

What if accounts can contain duplicate emails inside the same account?

The solution remains correct. Union-Find handles repeated unions safely: if two emails are already in the same group, the union operation returns without changing anything.

For output, grouping uses unique email keys from email_to_name, so duplicate appearances do not create duplicate output emails. The only added cost is a little repeated processing while scanning the input.

How would the solution change for streaming account updates?

Union-Find can handle new accounts incrementally. For each incoming account, add new emails, union them with the account’s first email, and update email_to_name.

The hard part is serving sorted merged-account output after every update. Union-Find is good at merging groups, but it is not designed for splitting groups or maintaining sorted member lists automatically. For frequent queries, each root could maintain a balanced sorted set of emails, merging smaller sets into larger sets during union. That improves query speed but increases implementation complexity and memory usage.

Can Union-Find handle account deletion?

Not cleanly. Standard Union-Find supports adding connections, but it does not support removing a connection and splitting a component if that connection was the only bridge between two groups.

If deletions matter, use a graph representation and recompute affected connected components, or use a more advanced dynamic connectivity data structure. For an interview version, the practical answer is usually to rebuild components from the remaining accounts unless the update volume is large enough to justify specialized machinery.