#721

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Accounts Merge

Merge accounts by connecting emails and returning each user's sorted email list using array scanning and hash lookup efficiently.

array hash table string depth first search breadth first search

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

Metric	Value
Time	O(NK \log {NK})
Space	O(NK)

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.

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.

terminal

Solution

Solution 1: Union-Find + Hash Table

Based on the problem description, we can use a union-find data structure to merge accounts with the same email address. The specific steps are as follows:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

class UnionFind:
    def __init__(self, n):
        self.p = list(range(n))
        self.size = [1] * n

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, a, b):
        pa, pb = self.find(a), self.find(b)
        if pa == pb:
            return False
        if self.size[pa] > self.size[pb]:
            self.p[pb] = pa
            self.size[pa] += self.size[pb]
        else:
            self.p[pa] = pb
            self.size[pb] += self.size[pa]
        return True


class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        uf = UnionFind(len(accounts))
        d = {}
        for i, (_, *emails) in enumerate(accounts):
            for email in emails:
                if email in d:
                    uf.union(i, d[email])
                else:
                    d[email] = i
        g = defaultdict(set)
        for i, (_, *emails) in enumerate(accounts):
            root = uf.find(i)
            g[root].update(emails)
        return [[accounts[root][0]] + sorted(emails) for root, emails in g.items()]

Continue Practicing

#1202 smallest string with swaps #839 similar string groups #924 minimize malware spread