Accounts Merge
Problem Description
Given a list of accounts where each element accounts[i] is a list of strings, the first element accounts[i][0] is the name, and the rest are emails belonging to that account.
Merge accounts that share at least one email. Two accounts share the same person if they have a common email address.
Return the merged accounts in any order. Each account should be formatted as: first element is the name, followed by a sorted list of unique emails.
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”]]
Constraints
1 ≤ accounts.length ≤ 10002 ≤ accounts[i].length ≤ 101 ≤ accounts[i][j].length ≤ 30
Union Emails, Not Accounts
Each email belongs to exactly one person. If two accounts share an email, all their emails belong to the same person. Model each email as a node. For each account, union all its emails together (they all belong to the same person). Then group emails by their root and pair with the account name.
Use a map from email to the account index that “owns” the name, so after merging you know which name to attach to each group.
Solution: Union-Find on Emails
import java.util.*;
class Solution {
private Map<String, String> parent = new HashMap<>();
private Map<String, Integer> rank = new HashMap<>();
public List<List<String>> accountsMerge(List<List<String>> accounts) {
Map<String, String> emailToName = new HashMap<>();
// initialize union-find for each email
for (List<String> account : accounts) {
String name = account.get(0);
for (int i = 1; i < account.size(); i++) {
String email = account.get(i);
parent.putIfAbsent(email, email);
rank.putIfAbsent(email, 0);
emailToName.put(email, name);
}
}
// union emails within the same account
for (List<String> account : accounts) {
for (int i = 2; i < account.size(); i++) {
union(account.get(1), account.get(i));
}
}
// group emails by their root
Map<String, TreeSet<String>> groups = new HashMap<>();
for (String email : parent.keySet()) {
String root = find(email);
groups.computeIfAbsent(root, k -> new TreeSet<>()).add(email);
}
List<List<String>> result = new ArrayList<>();
for (Map.Entry<String, TreeSet<String>> entry : groups.entrySet()) {
List<String> merged = new ArrayList<>();
merged.add(emailToName.get(entry.getKey()));
merged.addAll(entry.getValue()); // already sorted (TreeSet)
result.add(merged);
}
return result;
}
private String find(String x) {
if (!parent.get(x).equals(x)) parent.put(x, find(parent.get(x)));
return parent.get(x);
}
private void union(String x, String y) {
String px = find(x), py = find(y);
if (px.equals(py)) return;
int rx = rank.get(px), ry = rank.get(py);
if (rx < ry) parent.put(px, py);
else if (rx > ry) parent.put(py, px);
else { parent.put(py, px); rank.put(px, rx + 1); }
}
}from collections import defaultdict
class Solution:
def accountsMerge(self, accounts: list[list[str]]) -> list[list[str]]:
parent = {}
email_to_name = {}
def find(x: str) -> str:
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x: str, y: str):
parent[find(x)] = find(y)
for account in accounts:
name = account[0]
for email in account[1:]:
if email not in parent:
parent[email] = email
email_to_name[email] = name
union(account[1], email)
# group by root
groups = defaultdict(list)
for email in parent:
groups[find(email)].append(email)
return [
[email_to_name[root]] + sorted(emails)
for root, emails in groups.items()
]#include <vector>
#include <string>
#include <unordered_map>
#include <map>
#include <set>
class Solution {
std::unordered_map<std::string, std::string> parent;
std::string find(const std::string& x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
void unite(const std::string& x, const std::string& y) {
parent[find(x)] = find(y);
}
public:
std::vector<std::vector<std::string>> accountsMerge(std::vector<std::vector<std::string>>& accounts) {
std::unordered_map<std::string, std::string> emailToName;
for (auto& acc : accounts) {
for (int i = 1; i < (int)acc.size(); i++) {
if (!parent.count(acc[i])) parent[acc[i]] = acc[i];
emailToName[acc[i]] = acc[0];
if (i > 1) unite(acc[1], acc[i]);
}
}
std::map<std::string, std::set<std::string>> groups;
for (auto& [email, _] : parent) groups[find(email)].insert(email);
std::vector<std::vector<std::string>> result;
for (auto& [root, emails] : groups) {
std::vector<std::string> merged = {emailToName[root]};
merged.insert(merged.end(), emails.begin(), emails.end());
result.push_back(merged);
}
return result;
}
};Complexity Analysis:
- Time Complexity: O(n * k * alpha(n * k)) where n is accounts and k is max emails per account. Essentially O(n * k * log(n * k)) for sorting.
- Space Complexity: O(n * k) for the union-find structures.
Where it breaks: the emailToName map uses any account’s name for a given email. The problem guarantees that all accounts with the same email belong to the same person, so names will be consistent for merged groups.
Common Mistakes
- Unioning non-adjacent emails in an account instead of all to the first. Union every email to
account[1](the first email). Or union each consecutive pair. Both achieve the same connected component. - Forgetting to sort emails before adding to the result. The problem requires sorted emails per merged account.