Problem Description

You are given a list of accounts where each account is represented as a list of strings. The first string in each account list is the person's name, and the remaining strings are email addresses belonging to that account.

Your task is to merge accounts that belong to the same person. Two accounts belong to the same person if they share at least one common email address. Once two accounts are identified as belonging to the same person, all their emails should be combined.

Important points to consider:

• Even if two accounts have the same name, they might belong to different people (names are not unique)
• A person can have multiple accounts initially, but all accounts belonging to the same person will have the same name
• If account A shares an email with account B, and account B shares a different email with account C, then all three accounts belong to the same person (transitive property)

The output should be a list of merged accounts where:

• The first element is the person's name
• The remaining elements are all unique email addresses in sorted order
• The accounts themselves can be returned in any order

For example, if you have:

• ["John", "john@mail.com", "john123@mail.com"]
• ["John", "john123@mail.com", "john@work.com"]
• ["Mary", "mary@mail.com"]

The first two accounts share "john123@mail.com", so they belong to the same person and should be merged into:

• ["John", "john123@mail.com", "john@mail.com", "john@work.com"] (emails in sorted order)
• ["Mary", "mary@mail.com"]

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem involves accounts (nodes) that are connected through shared email addresses (edges). When two accounts share an email, they form a connection in an implicit graph structure.

Is it a tree?

• No: The connections between accounts can form cycles (account A connects to B, B connects to C, and C could connect back to A through shared emails), and accounts can have multiple connections, so it's not a tree structure.

Is the problem related to directed acyclic graphs?

• No: The relationships between accounts are undirected (if account A shares an email with account B, then B shares it with A) and can contain cycles.

Is the problem related to shortest paths?

• No: We're not finding shortest paths between accounts; we're identifying which accounts belong together.

Does the problem involve connectivity?

• Yes: The core of the problem is finding connected components - groups of accounts that are all connected through shared email addresses. Each connected component represents all accounts belonging to the same person.

Disjoint Set Union

• Yes: This is the suggested approach. DSU (Union-Find) is perfect for this problem as it efficiently handles merging sets (accounts) and finding which set an account belongs to.

Conclusion: While the flowchart leads us to DSU (which is what the solution uses), DFS is also a valid approach for this problem. After building the graph of email connections, we can use DFS to traverse each connected component, collecting all emails that belong to the same person. Both DSU and DFS effectively solve the connectivity problem of finding and merging accounts that share email addresses.

Intuition

The key insight is recognizing that this is fundamentally a graph connectivity problem. Each account can be thought of as a node, and when two accounts share an email address, they're connected by an edge. The challenge is that these connections are transitive - if account A shares an email with account B, and account B shares a different email with account C, then all three accounts belong to the same person.

Think of it like finding groups of friends on a social network. If person A knows person B, and person B knows person C, then they're all part of the same social circle, even if A and C don't directly know each other.

The Union-Find (Disjoint Set Union) data structure is perfect for this scenario because:

1. Efficient Merging: When we discover two accounts share an email, we can quickly merge them into the same group using union() operation.

2. Group Identification: We can easily find which group any account belongs to using find() operation.

3. Transitive Connections: Union-Find naturally handles transitive relationships - if we union A with B, then union B with C, the data structure automatically knows that A, B, and C are all in the same group.

The approach works by:

• First, iterating through all accounts and their emails
• Using a hash table to track which account index each email belongs to
• When we encounter an email that's already been seen, we know the current account and the previous account with that email belong to the same person, so we union them
• After processing all accounts, we use the Union-Find structure to group all emails by their root representative
• Finally, we construct the merged accounts using the grouped emails

This is more efficient than building an explicit graph and running DFS on each component, as Union-Find operations are nearly constant time with path compression and union by rank optimizations.

Learn more about Depth-First Search, Breadth-First Search, Union Find and Sorting patterns.

Solution Approach

The solution implements a Union-Find data structure with optimizations (path compression and union by size) to efficiently merge accounts. Let's walk through the implementation step by step:

1. Union-Find Data Structure Setup

First, we create a UnionFind class with the following components:

• self.p: Parent array where p[i] initially points to itself (each account is its own group)
• self.size: Tracks the size of each group for union by size optimization

The find() method uses path compression - when finding the root of a node, it directly connects all nodes in the path to the root, making future operations faster.

The union() method merges two groups by connecting the smaller group's root to the larger group's root (union by size), which keeps the tree balanced.

2. Building Email-to-Account Mapping

d = {}  # email -> account index mapping
for i, (_, *emails) in enumerate(accounts):
    for email in emails:
        if email in d:
            uf.union(i, d[email])  # merge current account with previous account
        else:
            d[email] = i  # map email to current account index

We iterate through each account and its emails:

• If an email hasn't been seen before, we map it to the current account's index in dictionary d
• If an email has been seen, it means the current account and the previously seen account share this email, so we union them

3. Grouping Emails by Root Account

g = defaultdict(set)
for i, (_, *emails) in enumerate(accounts):
    root = uf.find(i)
    g[root].update(emails)

After all unions are complete, we iterate through accounts again:

• Find the root representative for each account using uf.find(i)
• Add all emails from that account to the set associated with its root
• Using a set automatically handles duplicate emails across merged accounts

4. Constructing the Final Result

return [[accounts[root][0]] + sorted(emails) for root, emails in g.items()]

For each group (identified by its root):

• Take the name from the root account (all merged accounts have the same name)
• Sort the collected emails alphabetically
• Combine the name and sorted emails into a single list

The time complexity is O(N * α(N)) for union-find operations (where α is the inverse Ackermann function, practically constant) plus O(E log E) for sorting emails, where N is the number of accounts and E is the total number of emails.

Example Walkthrough

Let's walk through a small example with these accounts:

• Account 0: ["Alice", "alice@gmail.com", "alice@work.com"]
• Account 1: ["Alice", "alice@work.com", "alice@yahoo.com"]
• Account 2: ["Bob", "bob@gmail.com"]
• Account 3: ["Alice", "alice@yahoo.com", "alice@hotmail.com"]

Step 1: Initialize Union-Find

• Create UnionFind with 4 accounts
• Parent array: [0, 1, 2, 3] (each account points to itself)
• Size array: [1, 1, 1, 1]

Step 2: Build Email-to-Account Mapping

Processing Account 0:

• alice@gmail.com → not seen, map to account 0: d = {"alice@gmail.com": 0}
• alice@work.com → not seen, map to account 0: d = {"alice@gmail.com": 0, "alice@work.com": 0}

Processing Account 1:

• alice@work.com → already seen (mapped to 0), so union(1, 0)
  • After union: parent = [0, 0, 2, 3], size = [2, 1, 1, 1]
• alice@yahoo.com → not seen, map to account 1: d = {..., "alice@yahoo.com": 1}

Processing Account 2:

• bob@gmail.com → not seen, map to account 2: d = {..., "bob@gmail.com": 2}

Processing Account 3:

• alice@yahoo.com → already seen (mapped to 1), so union(3, 1)
  • find(1) returns 0 (since 1's parent is 0)
  • So we actually union(3, 0)
  • After union: parent = [0, 0, 2, 0], size = [3, 1, 1, 1]
• alice@hotmail.com → not seen, map to account 3

Step 3: Group Emails by Root

• Account 0: find(0) = 0, add emails to group 0
• Account 1: find(1) = 0, add emails to group 0
• Account 2: find(2) = 2, add emails to group 2
• Account 3: find(3) = 0, add emails to group 0

Groups formed:

• Group 0: {"alice@gmail.com", "alice@work.com", "alice@yahoo.com", "alice@hotmail.com"}
• Group 2: {"bob@gmail.com"}

Step 4: Construct Final Result

• Group 0: ["Alice", "alice@gmail.com", "alice@hotmail.com", "alice@work.com", "alice@yahoo.com"] (sorted)
• Group 2: ["Bob", "bob@gmail.com"]

The final output shows that accounts 0, 1, and 3 all belonged to the same Alice and were successfully merged through their shared emails.

Solution Implementation

Time and Space Complexity

The time complexity is O(n × m × α(n) + E × log E), where:

• n is the number of accounts
• m is the average number of emails per account
• α(n) is the inverse Ackermann function (practically constant, nearly O(1))
• E is the total number of unique emails across all accounts

Breaking down the operations:

1. First loop iterates through all accounts and emails: O(n × m) operations, each with a find operation that takes O(α(n)) time
2. Second loop iterates through all accounts and emails again: O(n × m) with find operations
3. Final list comprehension sorts emails for each merged group: O(E × log E) in the worst case when all emails belong to one group

Since α(n) is effectively constant and E ≤ n × m, the overall time complexity simplifies to O(n × m × log(n × m)) or approximately O(n × log n) when considering m as a constant factor in typical use cases.

The space complexity is O(n + E), where:

• Union-Find structure uses O(n) space for parent and size arrays
• Dictionary d stores up to E unique email-to-index mappings: O(E)
• DefaultDict g stores all unique emails: O(E)
• Output list contains all accounts and emails: O(n × m)

Since E ≤ n × m, the space complexity is O(n × m), which simplifies to O(n) when m is considered constant.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting That Names Are Not Unique Identifiers

Pitfall: A common mistake is assuming that accounts with the same name belong to the same person and should be merged. This leads to incorrectly merging accounts of different people who happen to have the same name.

Example of the mistake:

# WRONG: Grouping by name first
name_to_accounts = defaultdict(list)
for i, account in enumerate(accounts):
    name = account[0]
    name_to_accounts[name].append(i)
    # Then trying to merge within each name group

Why it's wrong: Consider these accounts:

• ["John", "john1@mail.com"]
• ["John", "john2@mail.com"]
• ["John", "john1@mail.com", "john3@mail.com"]

The first and third accounts should be merged (they share john1@mail.com), but the second account belongs to a different John and should remain separate.

Solution: Only use email addresses to determine if accounts should be merged. The name is just metadata that gets carried along with the merged account.

2. Not Handling the Transitive Property of Account Relationships

Pitfall: Only checking direct email overlaps between pairs of accounts without considering transitive relationships.

Example of the mistake:

# WRONG: Only checking direct overlaps
merged = []
used = set()
for i, account1 in enumerate(accounts):
    if i in used:
        continue
    emails = set(account1[1:])
    for j, account2 in enumerate(accounts[i+1:], i+1):
        if any(email in emails for email in account2[1:]):
            emails.update(account2[1:])
            used.add(j)
    merged.append([account1[0]] + sorted(emails))

Why it's wrong: This approach might miss transitive connections. For example:

• Account A: ["John", "a@mail.com", "b@mail.com"]
• Account B: ["John", "b@mail.com", "c@mail.com"]
• Account C: ["John", "c@mail.com", "d@mail.com"]

Account A connects to B through b@mail.com, and B connects to C through c@mail.com. All three should be merged, but a simple pairwise check might miss the A-C connection.

Solution: Use Union-Find (as in the provided solution) or graph traversal (DFS/BFS) to properly handle transitive relationships.

3. Modifying the Parent Array Without Path Compression

Pitfall: In the Union-Find implementation, directly modifying the parent array without proper path compression can lead to inefficient operations and potentially incorrect results.

Example of the mistake:

# WRONG: Simple find without path compression
def find(self, x):
    while self.parent[x] != x:
        x = self.parent[x]
    return x

Why it's wrong: Without path compression, the tree can become unbalanced, leading to O(n) find operations in the worst case. This degrades overall performance from nearly O(n) to O(n²).

Solution: Always implement path compression in the find operation:

def find(self, x):
    if self.parent[x] != x:
        self.parent[x] = self.find(self.parent[x])  # Path compression
    return self.parent[x]

4. Not Deduplicating Emails in the Final Result

Pitfall: When collecting emails from multiple accounts into a merged account, forgetting to deduplicate them.

Example of the mistake:

# WRONG: Using list instead of set
root_to_emails = defaultdict(list)
for account_index, account_data in enumerate(accounts):
    root_index = union_find.find(account_index)
    root_to_emails[root_index].extend(account_data[1:])  # Duplicates!

Why it's wrong: If multiple original accounts share emails, those emails will appear multiple times in the merged result.

Solution: Use a set to automatically handle deduplication:

root_to_emails = defaultdict(set)
for account_index, account_data in enumerate(accounts):
    root_index = union_find.find(account_index)
    root_to_emails[root_index].update(account_data[1:])  # Set handles duplicates