Given a list of accounts where each element accounts[i] is a list of strings, where the first element 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 the following format: the first element of each account is the name, and the rest of the elements are emails in sorted order. The accounts themselves can be returned in any order.

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"]]
Explanation:
The first and second John's accounts are merged because they share the email "johnsmith@mail.com".
The third John's account is not merged because it doesn't share any email with the other accounts.

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

Constraints

  • 1 <= accounts.length <= 1000
  • 2 <= accounts[i].length <= 10
  • 1 <= accounts[i][0].length <= 10
  • accounts[i][j] for j > 0 is a valid email.

Thinking Process

  1. Email as Unique Identifier: Names can be duplicated, but emails are unique
  • DFS explores one branch fully before backtracking.
  • Mark visited nodes to avoid cycles on graphs.
  • Return aggregated results from children to the parent.
Tree DFS (bottom-up) 3 9 20 15 7 post-order: combine left + right + 1

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Recursive DFS (this problem) O(n) O(h) stack Natural for trees and graphs
Iterative DFS (stack) O(n) O(n) Avoid recursion depth limits
DFS with memoization O(n) O(n) Overlapping subproblems on graphs
Backtracking DFS O(2^n) typical O(n) Enumerate choices with pruning

Solution

Solution: Union-Find (Disjoint Set Union)

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))

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

    def unionSet(self, x, y):
        px = self.find(x)
        py = self.find(y)
        self.parent[py] = px


class Solution:
    def accountsMerge(self, accounts):
        emailToIdx = {}
        emailToName = {}

        # 1: Assign ID to each email
        idx = 0
        for account in accounts:
            name = account[0]
            for i in range(1, len(account)):
                email = account[i]
                if email not in emailToIdx:
                    emailToIdx[email] = idx
                    idx += 1
                emailToName[email] = name

        uf = UnionFind(idx)

        # 2: Union emails in same account
        for account in accounts:
            firstEmail = account[1]
            firstIdx = emailToIdx[firstEmail]

            for i in range(2, len(account)):
                nextEmail = account[i]
                uf.unionSet(firstIdx, emailToIdx[nextEmail])

        # 3: Group by root
        from collections import defaultdict
        idxToEmails = defaultdict(list)

        for email in emailToIdx:
            root = uf.find(emailToIdx[email])
            idxToEmails[root].append(email)

        # 4: Build result
        merged = []
        for emails in idxToEmails.values():
            emails.sort()
            name = emailToName[emails[0]]

            merged.append([name] + emails)

        return merged

Solution Explanation

Approach: Recursive DFS (this problem)

Key idea: 1. Email as Unique Identifier: Names can be duplicated, but emails are unique

How the code works:

  1. Email as Unique Identifier: Names can be duplicated, but emails are unique
    • DFS explores one branch fully before backtracking.
    • Mark visited nodes to avoid cycles on graphs.
    • Return aggregated results from children to the parent.

Walkthrough — 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"]], expected 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 accounts are merged because they share the email “johnsmith@mail.com”. The third John’s account is not merged because it doesn’t share any email with the other accounts.

Algorithm Explanation:

  1. Union-Find Class (Lines 1-23):
    • Constructor: Initialize parent array where each element is its own parent
    • unionSet: Union two sets by making idx2’s root point to idx1’s root
    • find: Find root with path compression (flattens the tree for efficiency)
  2. Step 1: Assign IDs (Lines 30-41):
    • Iterate through all accounts
    • For each email in an account:
      • If email not seen before, assign a unique id and map to name
      • Store mappings: emailToIdx[email] = id and emailToName[email] = name
  3. Step 2: Union Emails (Lines 43-53):
    • For each account, union all emails in that account
    • Strategy: Union all emails to the first email in the account
    • This groups all emails from the same account together
  4. Step 3: Group by Root (Lines 55-61):
    • For each email, find its root parent using uf.find()
    • Group emails by their root parent in idxToEmails
    • Emails with the same root belong to the same merged account
  5. Step 4: Build Result (Lines 63-73):
    • For each group of emails:
      • Sort emails alphabetically
      • Get the name from the first email (all emails in group have same name)
      • Create account: [name, email1, email2, ...]
      • Add to result

Why This Works:

  • Union-Find Groups: Emails in the same account are unioned, so they share the same root
  • Transitive Merging: If account A shares email with B, and B shares with C, then A, B, C are all merged (transitive property)
  • Path Compression: Makes find operations efficient (nearly O(1) amortized)
  • Email as Key: Using emails (not names) correctly handles duplicate names

Example Walkthrough:

For accounts = [["John","a@mail.com","b@mail.com"],["John","a@mail.com","c@mail.com"],["Mary","d@mail.com"]]:

Step 1: Assign IDs
emailToIdx: {
    "a@mail.com": 0,
    "b@mail.com": 1,
    "c@mail.com": 2,
    "d@mail.com": 3
}
emailToName: {
    "a@mail.com": "John",
    "b@mail.com": "John",
    "c@mail.com": "John",
    "d@mail.com": "Mary"
}

Step 2: Union emails
Account 1: ["John","a@mail.com","b@mail.com"]
  - Union(0, 1): parent[1] = 0
  - parent = [0, 0, 2, 3]

Account 2: ["John","a@mail.com","c@mail.com"]
  - Union(0, 2): parent[2] = 0
  - parent = [0, 0, 0, 3]

Account 3: ["Mary","d@mail.com"]
  - No union needed (only one email)
  - parent = [0, 0, 0, 3]

Step 3: Group by root
idxToEmails: {
    0: ["a@mail.com", "b@mail.com", "c@mail.com"],
    3: ["d@mail.com"]
}

Step 4: Build result
Group 0: 
  - Sort: ["a@mail.com", "b@mail.com", "c@mail.com"]
  - Name: "John"
  - Account: ["John", "a@mail.com", "b@mail.com", "c@mail.com"]

Group 3:
  - Sort: ["d@mail.com"]
  - Name: "Mary"
  - Account: ["Mary", "d@mail.com"]

Result: [
    ["John", "a@mail.com", "b@mail.com", "c@mail.com"],
    ["Mary", "d@mail.com"]
]

Complexity Analysis:

  • Time Complexity: O(n × k × α(n × k) + n × k × log(n × k))
    • n = number of accounts, k = average emails per account
    • O(n × k) for assigning IDs
    • O(n × k × α(n × k)) for union operations (α is inverse Ackermann, nearly constant)
    • O(n × k × log(n × k)) for sorting emails in each group
    • Total: O(n × k × log(n × k)) dominated by sorting
  • Space Complexity: O(n × k)
    • emailToIdx: O(n × k) for all emails
    • emailToName: O(n × k) for all emails
    • idxToEmails: O(n × k) for grouped emails
    • parent array: O(n × k)

      Common Mistakes

  1. Single email per account: [["John","a@mail.com"]] → return [["John","a@mail.com"]]
  2. No shared emails: All accounts remain separate
  3. All emails shared: All accounts merge into one

  4. Duplicate emails in same account: Handled correctly (only assigned one ID)

  5. Using names as keys: Names can be duplicated, causing incorrect merging
  6. Not sorting emails: Result must have sorted emails
  7. Wrong union logic: Must union all emails in an account, not just pairs
  8. Missing path compression: Without it, find can be O(n) instead of O(α(n))
  9. Name mismatch: Assuming all emails in merged account have same name (they do, but need to verify)

Key Takeaways

  1. Email as Unique Identifier: Names can be duplicated, but emails are unique
  2. Union-Find for Grouping: Efficiently groups emails that belong together
  3. Transitive Merging: If A shares email with B, and B shares with C, then A, B, C are merged
  4. Path Compression: Critical for efficiency in Union-Find operations

References

Template Reference