Why it fails: This approach is highly inefficient. Checking for intersections between arbitrary lists takes significant time. Furthermore, the "ripple effect" of merging (where A connects to B, and B connects to C, implying A connects to C) might require many passes through the entire list to propagate. In the worst case, the time complexity approaches $O(N^3 \times K)$, where $N$ is the number of accounts and $K$ is the max number of emails. This leads to Time Limit Exceeded (TLE) on larger inputs.

Core Insight for Accounts Merge

The key intuition is to shift our perspective from "merging accounts" to "grouping emails."

1. Emails are Nodes: Think of every unique email address as a node in a graph.
2. Accounts are Edges: If an account entry looks like ["John", "a@mail.com", "b@mail.com"], this implies that a@mail.com and b@mail.com are connected. They belong to the same component.
3. Transitivity: If Account 1 has emails {A, B} and Account 2 has emails {B, C}, the common email B acts as a bridge. A is connected to B, and B is connected to C; therefore, A, B, and C are all part of the same connected component.

Visual Description: Imagine a graph where every unique email is a vertex. Iterate through each account. For an account with emails $[e_1, e_2, e_3]$, draw an edge between $e_1-e_2$ and $e_2-e_3$. Once we process all accounts, the graph will consist of several isolated clusters (connected components). Each cluster represents one unique person. We can then collect all emails in a cluster and assign them the correct name.

Algorithm Strategy: Graph - Union-Find (Disjoint Set Union - DSU)

We will utilize the Union-Find data structure to manage the disjoint sets of emails.

1. Initialization: We need a DSU structure capable of handling string keys (emails). We can implement this using a hash map where parent[email] = parent_email.
2. Mapping Owners: We also need a map emailToName to remember which name is associated with each email. Since all emails in a connected component belong to the same person, we only need to record the name for one email in the component (or all of them; the name is consistent).
3. Union Operations:
   • Iterate through each account in the input list.
   • For each account, select the first email as a "pivot".
   • Perform a Union operation between the first email and every subsequent email in that account's list. This effectively stitches all emails in that account into a single set.
4. Grouping:
   • After processing all accounts, iterate through every unique email encountered.
   • Find the representative (root) of that email using Find(email).
   • Group emails into a list keyed by their representative root.
5. Formatting:
   • For each group, look up the name using the representative email.
   • Sort the emails within the group.
   • Construct the final result list.

Execution Flow

Let's trace the algorithm with accounts = [["John", "a@m.com", "b@m.com"], ["John", "b@m.com", "c@m.com"], ["Mary", "d@m.com"]].

1. Initialize: parent = {}, emailToName = {}.
2. Process Account 1 ["John", "a@m.com", "b@m.com"]:
   • Map a@m.com -> "John", b@m.com -> "John".
   • Union("a@m.com", "b@m.com"). Parent of b becomes a.
3. Process Account 2 ["John", "b@m.com", "c@m.com"]:
   • Map c@m.com -> "John".
   • Union("b@m.com", "c@m.com").
   • Find("b@m.com") leads to a@m.com. Find("c@m.com") is c@m.com.
   • Parent of c becomes a.
   • Now a, b, and c are in the same set rooted at a.
4. Process Account 3 ["Mary", "d@m.com"]:
   • Map d@m.com -> "Mary".
   • Only one email, no union needed (or union with itself). Root is d.
5. Build Components:
   • Iterate all emails: a, b, c, d.
   • Find(a) -> a. Group a: [a]
   • Find(b) -> a. Group a: [a, b]
   • Find(c) -> a. Group a: [a, b, c]
   • Find(d) -> d. Group d: [d]
6. Format Output:
   • Group a: Name is "John". Sort emails: ["a@m.com", "b@m.com", "c@m.com"]. Result: ["John", "a...", "b...", "c..."].
   • Group d: Name is "Mary". Sort emails: ["d@m.com"]. Result: ["Mary", "d..."].

Proof of Correctness

The correctness relies on the properties of the Disjoint Set Union structure.

1. Connectivity: The problem defines two accounts as "connected" if they share an email. DSU strictly enforces this: by uniting all emails in a single account, and then uniting emails across accounts via their intersections, we build the transitive closure of the connectivity graph.
2. Disjoint Sets: DSU guarantees that after all operations, elements are partitioned into disjoint sets. No email can belong to two different resulting people.
3. Invariant: The emailToName mapping remains valid because the problem statement guarantees that all accounts belonging to the same person have the same name. Therefore, any email in a connected component can provide the correct name.

Reference Implementation

C++ Solution for LeetCode 721

cpp
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
#include <map>

using namespace std;

class Solution {
    // DSU Implementation
    unordered_map<string, string> parent;
    
    string find(string email) {
        // Path compression
        if (parent[email] == email) {
            return email;
        }
        return parent[email] = find(parent[email]);
    }
    
    void unionSets(string e1, string e2) {
        string root1 = find(e1);
        string root2 = find(e2);
        if (root1 != root2) {
            parent[root1] = root2; // Union
        }
    }

public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        unordered_map<string, string> emailToName;
        
        // 1. Initialize DSU and map emails to names
        for (const auto& acc : accounts) {
            string name = acc[0];
            for (int i = 1; i < acc.size(); ++i) {
                string email = acc[i];
                emailToName[email] = name;
                if (parent.find(email) == parent.end()) {
                    parent[email] = email;
                }
                
                // Union current email with the previous one in the list
                if (i > 1) {
                    unionSets(acc[i], acc[i-1]);
                }
            }
        }
        
        // 2. Group emails by their root parent
        unordered_map<string, vector<string>> components;
        for (auto& pair : parent) {
            string email = pair.first;
            string root = find(email);
            components[root].push_back(email);
        }
        
        // 3. Format the result
        vector<vector<string>> result;
        for (auto& pair : components) {
            vector<string> emails = pair.second;
            sort(emails.begin(), emails.end());
            
            vector<string> account;
            account.push_back(emailToName[pair.first]); // Add Name
            account.insert(account.end(), emails.begin(), emails.end()); // Add Sorted Emails
            result.push_back(account);
        }
        
        return result;
    }
};

Java Solution for LeetCode 721

java
import java.util.*;

class Solution {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        Map<String, String> parent = new HashMap<>();
        Map<String, String> emailToName = new HashMap<>();
        
        // 1. Initialize DSU and perform Unions
        for (List<String> account : accounts) {
            String name = account.get(0);
            for (int i = 1; i < account.size(); i++) {
                String email = account.get(i);
                emailToName.put(email, name);
                parent.putIfAbsent(email, email);
                
                if (i > 1) {
                    union(parent, account.get(i), account.get(i - 1));
                }
            }
        }
        
        // 2. Group emails by Root
        Map<String, List<String>> components = new HashMap<>();
        for (String email : parent.keySet()) {
            String root = find(parent, email);
            components.computeIfAbsent(root, k -> new ArrayList<>()).add(email);
        }
        
        // 3. Format Output
        List<List<String>> result = new ArrayList<>();
        for (String root : components.keySet()) {
            List<String> emails = components.get(root);
            Collections.sort(emails);
            
            List<String> mergedAccount = new ArrayList<>();
            mergedAccount.add(emailToName.get(root)); // Add Name
            mergedAccount.addAll(emails);            // Add Emails
            result.add(mergedAccount);
        }
        
        return result;
    }
    
    private String find(Map<String, String> parent, String s) {
        if (!parent.get(s).equals(s)) {
            parent.put(s, find(parent, parent.get(s))); // Path Compression
        }
        return parent.get(s);
    }
    
    private void union(Map<String, String> parent, String s1, String s2) {
        String root1 = find(parent, s1);
        String root2 = find(parent, s2);
        if (!root1.equals(root2)) {
            parent.put(root1, root2);
        }
    }
}

Python Solution for LeetCode 721

python
class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        parent = {}
        email_to_name = {}

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

        def union(x, y):
            rootX = find(x)
            rootY = find(y)
            if rootX != rootY:
                parent[rootX] = rootY

        # 1. Initialize DSU and Union emails within each account
        for acc in accounts:
            name = acc[0]
            first_email = acc[1]
            for email in acc[1:]:
                if email not in parent:
                    parent[email] = email
                email_to_name[email] = name
                union(first_email, email)
        
        # 2. Group emails by their root
        components = {}
        for email in parent:
            root = find(email)
            if root not in components:
                components[root] = []
            components[root].append(email)
        
        # 3. Format Output
        result = []
        for root, emails in components.items():
            result.append([email_to_name[root]] + sorted(emails))
            
        return result