# Accounts Merge
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/accounts-merge)
Canonical: https://scaleengineer.com/dsa/problems/accounts-merge
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting), [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Array, Hash Table, String
**Companies:** [Roblox](https://scaleengineer.com/companies/roblox), [Rippling](https://scaleengineer.com/companies/rippling), [Snap](https://scaleengineer.com/companies/snap), [PhonePe](https://scaleengineer.com/companies/phonepe), [Pinterest](https://scaleengineer.com/companies/pinterest), [Palantir Technologies](https://scaleengineer.com/companies/palantir-technologies)
---
## Problem
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**.

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

**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.

# Approaches
## Graph Traversal (DFS/BFS)
This approach models the problem as finding connected components in a graph. Each email is treated as a node, and an edge is created between two emails if they appear in the same initial account. By traversing this graph using algorithms like Depth-First Search (DFS) or Breadth-First Search (BFS), we can identify groups of connected emails, which represent the merged accounts.
**Time:** O(A log A), where A is the total size of all strings in the input `accounts`. Building the graph takes O(A). Traversing the entire graph also takes O(A). The dominant factor is sorting the emails within each merged component. In the worst case, all emails belong to one person, and sorting them takes O(A log A). · **Space:** O(A), where A is the total size of all strings in the input `accounts`. This space is required for the adjacency list (`graph`), the `emailToName` map, the `visited` set, and the stack for DFS.
**Pros:** It's a conceptually intuitive approach for connectivity problems.; The logic is relatively straightforward if you are familiar with graph traversal algorithms.
**Cons:** The graph construction and traversal might have higher constant factor overheads compared to a specialized Union-Find data structure.; Explicitly storing the graph can consume significant memory, especially for densely connected accounts.
### Explanation
The first step is to build the graph structure. We use a hash map as an adjacency list, where each key is an email and the value is a list of emails it's connected to. We also maintain a separate map to link each email to its owner's name. We iterate through all the accounts; for each account, we link all its emails to the first email in that account, effectively creating a star-shaped connection for each account's emails. 

Once the graph is built, we find the connected components. We iterate through all the emails we've encountered. If an email hasn't been visited yet, we begin a traversal (DFS is used in the example below) to find all emails in its component. We use a `visited` set to avoid redundant traversals. All emails found in a single traversal belong to the same person. We collect these emails, sort them, find the associated name, and add the complete, merged account to our results.

```java
import java.util.*;

class Solution {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        Map<String, String> emailToName = new HashMap<>();
        Map<String, List<String>> graph = new HashMap<>();

        // Build the graph and emailToName map
        for (List<String> account : accounts) {
            String name = account.get(0);
            String firstEmail = account.get(1);
            for (int i = 1; i < account.size(); i++) {
                String email = account.get(i);
                emailToName.put(email, name);
                // Add edges between the first email and all other emails in the account
                graph.computeIfAbsent(firstEmail, k -> new ArrayList<>()).add(email);
                graph.computeIfAbsent(email, k -> new ArrayList<>()).add(firstEmail);
            }
        }

        List<List<String>> mergedAccounts = new ArrayList<>();
        Set<String> visited = new HashSet<>();

        // Traverse the graph to find connected components using DFS
        for (String email : graph.keySet()) {
            if (!visited.contains(email)) {
                List<String> component = new ArrayList<>();
                Stack<String> stack = new Stack<>();
                
                stack.push(email);
                visited.add(email);

                while (!stack.isEmpty()) {
                    String currentEmail = stack.pop();
                    component.add(currentEmail);
                    
                    if (graph.containsKey(currentEmail)) {
                        for (String neighbor : graph.get(currentEmail)) {
                            if (!visited.contains(neighbor)) {
                                visited.add(neighbor);
                                stack.push(neighbor);
                            }
                        }
                    }
                }
                
                Collections.sort(component);
                component.add(0, emailToName.get(email));
                mergedAccounts.add(component);
            }
        }

        return mergedAccounts;
    }
}
```
### Algorithm
- Create an adjacency list `graph` where keys are emails and values are lists of connected emails.
- Create a map `emailToName` to associate each email with the account holder's name.
- Iterate through each account in the input list. For each account, connect all its emails by adding edges between the first email and every other email in the account. Populate the `emailToName` map simultaneously.
- Initialize a `visited` set to keep track of processed emails.
- Iterate through all emails. If an email has not been visited, start a graph traversal (like DFS or BFS) from it.
- The traversal will discover a connected component of emails. Collect all emails in this component.
- Mark all emails in the component as visited.
- Sort the collected list of emails alphabetically.
- Retrieve the owner's name from the `emailToName` map and prepend it to the sorted list.
- Add the resulting merged account to the final list.
- Repeat until all emails have been visited.

## Union-Find (Disjoint Set Union)
A more optimized approach uses the Union-Find data structure, which is specifically designed for problems involving disjoint sets. Each email is an element, and we want to group emails belonging to the same person into a single set. We iterate through the accounts and use the `union` operation to merge the sets of any emails that appear together. After processing all accounts, the disjoint sets represent the merged accounts.
**Time:** O(A log A), where A is the total size of all strings. The passes for mapping and performing unions take O(A * α(N)), where α is the very slow-growing inverse Ackermann function, making it nearly linear O(A). The bottleneck remains the final step of sorting the emails in each component, which can be up to O(A log A) in the worst case. · **Space:** O(A), where A is the total size of all strings in the input. Space is used for the `emailToName` and `emailToId` maps, the Union-Find arrays (`parent`, `rank`), and the map for grouping components.
**Pros:** Extremely efficient for modeling and solving disjoint set problems.; The `union` and `find` operations have an amortized time complexity that is nearly constant.; Generally faster in practice for the connectivity part of the problem than graph traversal.
**Cons:** The implementation is more complex, requiring multiple data structures (maps for string-to-ID conversion, the DSU array) and several passes over the data.; It can be less intuitive than a direct graph traversal if one is not familiar with the Union-Find data structure.
### Explanation
This method avoids building an explicit graph. Instead, it relies on the Union-Find data structure to track connectivity. We first map every unique email to an integer ID to use with an array-based Union-Find implementation. We also map each email to its owner's name.

We then iterate through each account and call `union` on the IDs of its emails. This links all emails within an account into the same component. The `find` operation, enhanced with path compression, makes this process highly efficient.

After all unions are performed, we group the emails. We iterate through our email-to-ID map, find the representative (root) for each email's set, and add the email to a list associated with that root. This gives us our components. Finally, we sort the emails in each component, prepend the correct name, and build the final list of merged accounts.

```java
import java.util.*;

class Solution {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        Map<String, String> emailToName = new HashMap<>();
        Map<String, Integer> emailToId = new HashMap<>();
        int id = 0;

        // First pass: map emails to IDs and names
        for (List<String> account : accounts) {
            String name = account.get(0);
            for (int i = 1; i < account.size(); i++) {
                String email = account.get(i);
                if (!emailToId.containsKey(email)) {
                    emailToId.put(email, id++);
                }
                emailToName.put(email, name);
            }
        }

        UnionFind dsu = new UnionFind(id);

        // Second pass: union emails in the same account
        for (List<String> account : accounts) {
            int firstEmailId = emailToId.get(account.get(1));
            for (int i = 2; i < account.size(); i++) {
                int nextEmailId = emailToId.get(account.get(i));
                dsu.union(firstEmailId, nextEmailId);
            }
        }

        // Third pass: group emails by their root
        Map<Integer, List<String>> components = new HashMap<>();
        for (String email : emailToId.keySet()) {
            int emailId = emailToId.get(email);
            int rootId = dsu.find(emailId);
            components.computeIfAbsent(rootId, k -> new ArrayList<>()).add(email);
        }

        // Final pass: sort emails and format output
        List<List<String>> mergedAccounts = new ArrayList<>();
        for (List<String> componentEmails : components.values()) {
            Collections.sort(componentEmails);
            String name = emailToName.get(componentEmails.get(0));
            componentEmails.add(0, name);
            mergedAccounts.add(componentEmails);
        }

        return mergedAccounts;
    }
}

class UnionFind {
    int[] parent;
    int[] rank;

    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    public int find(int i) {
        if (parent[i] == i) {
            return i;
        }
        return parent[i] = find(parent[i]); // Path compression
    }

    public void union(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);
        if (rootI != rootJ) {
            // Union by rank
            if (rank[rootI] > rank[rootJ]) {
                parent[rootJ] = rootI;
            } else if (rank[rootI] < rank[rootJ]) {
                parent[rootI] = rootJ;
            } else {
                parent[rootJ] = rootI;
                rank[rootI]++;
            }
        }
    }
}
```
### Algorithm
- Create a Union-Find (Disjoint Set Union) data structure.
- Create helper maps: `emailToName` to store the owner's name for each email, and `emailToId` to assign a unique integer ID to each email.
- Iterate through all accounts to populate `emailToName` and `emailToId`. This pass determines the total number of unique emails.
- Initialize the Union-Find structure with the number of unique emails.
- Iterate through the accounts again. For each account, perform a `union` operation on the IDs of all its emails, merging them into a single set.
- Create a map `rootIdToEmails` to group emails by their component's root ID.
- Iterate through all unique emails. For each email, find the root of its set using the `find` operation and add the email to the corresponding list in `rootIdToEmails`.
- For each group of emails in `rootIdToEmails`:
  - Sort the list of emails.
  - Retrieve the owner's name using any email from the list and the `emailToName` map.
  - Prepend the name to the sorted list and add it to the final result.

# Solutions
### Java

```java
class Solution {
private
  int[] p;
public
  List<List<String>> accountsMerge(List<List<String>> accounts) {
    int n = accounts.size();
    p = new int[n];
    for (int i = 0; i < n; ++i) {
      p[i] = i;
    }
    Map<String, Integer> emailId = new HashMap<>();
    for (int i = 0; i < n; ++i) {
      List<String> account = accounts.get(i);
      String name = account.get(0);
      for (int j = 1; j < account.size(); ++j) {
        String email = account.get(j);
        if (emailId.containsKey(email)) {
          p[find(i)] = find(emailId.get(email));
        } else {
          emailId.put(email, i);
        }
      }
    }
    Map<Integer, Set<String>> mp = new HashMap<>();
    for (int i = 0; i < n; ++i) {
      List<String> account = accounts.get(i);
      for (int j = 1; j < account.size(); ++j) {
        String email = account.get(j);
        mp.computeIfAbsent(find(i), k->new HashSet<>()).add(email);
      }
    }
    List<List<String>> res = new ArrayList<>();
    for (Map.Entry<Integer, Set<String>> entry : mp.entrySet()) {
      List<String> t = new LinkedList<>();
      t.addAll(entry.getValue());
      Collections.sort(t);
      t.add(0, accounts.get(entry.getKey()).get(0));
      res.add(t);
    }
    return res;
  }
private
  int find(int x) {
    if (p[x] != x) {
      p[x] = find(p[x]);
    }
    return p[x];
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> p;
  vector<vector<string>> accountsMerge(vector<vector<string>> &accounts) {
    int n = accounts.size();
    p.resize(n);
    for (int i = 0; i < n; ++i)
      p[i] = i;
    unordered_map<string, int> emailId;
    for (int i = 0; i < n; ++i) {
      auto account = accounts[i];
      auto name = account[0];
      for (int j = 1; j < account.size(); ++j) {
        string email = account[j];
        if (emailId.count(email))
          p[find(i)] = find(emailId[email]);
        else
          emailId[email] = i;
      }
    }
    unordered_map<int, unordered_set<string>> mp;
    for (int i = 0; i < n; ++i) {
      auto account = accounts[i];
      for (int j = 1; j < account.size(); ++j) {
        string email = account[j];
        mp[find(i)].insert(email);
      }
    }
    vector<vector<string>> ans;
    for (auto &[i, emails] : mp) {
      vector<string> t;
      t.push_back(accounts[i][0]);
      for (string email : emails)
        t.push_back(email);
      sort(t.begin() + 1, t.end());
      ans.push_back(t);
    }
    return ans;
  }
  int find(int x) {
    if (p[x] != x) {
      p[x] = find(p[x]);
    }
    return p[x];
  }
};

```

### Python

```python
class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]: def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] n = len(accounts) p = list(range(n)) email_id = {} for i, account in enumerate(accounts): name = account[0] for email in account[1:]: if email in email_id: p[find(i)] = find(email_id[email]) else: email_id[email] = i mp = defaultdict(set) for i, account in enumerate(accounts): for email in account[1:]: mp[find(i)]. add(email) ans = [] for i, emails in mp . items(): t = [accounts[i][0]] t . extend(sorted(emails)) ans . append(t) return ans

```