Given a list of accounts, each accounts[i] = [name, email1, email2, ...], merge accounts that share at least one email — two accounts belong to the same person if they share ANY email, even transitively through a third account. Return the merged accounts, each with the name first, followed by all unique emails sorted alphabetically.
Example 1
Input: accounts = [["John","j1@m.com","j2@m.com"],["John","j3@m.com"],["John","j1@m.com","j4@m.com"]]
Output: [["John","j1@m.com","j2@m.com","j4@m.com"],["John","j3@m.com"]]
Explanation: Accounts 1 and 3 share j1@m.com, so they merge. Account 2 shares nothing with either, stays separate.
1 <= accounts.length <= 10002 <= accounts[i].length <= 10Emails consist of lowercase letters, digits, '+', '.', and '@'This looks nothing like a graph problem on the surface, but each email is a NODE, and two emails in the same account are UNIONed together.
After unioning, group emails by their root parent — each group is one merged account.
public List<List<String>> accountsMerge(List<List<String>> accounts) {
Map<String, String> parent = new HashMap<>();
Map<String, String> emailToName = new HashMap<>();
for (List<String> acc : accounts) {
String name = acc.get(0);
for (int i = 1; i < acc.size(); i++) {
String email = acc.get(i);
parent.putIfAbsent(email, email);
emailToName.put(email, name);
union(parent, acc.get(1), email); // union every email in this account with the first one
}
}
Map<String, TreeSet<String>> groups = new HashMap<>();
for (String email : parent.keySet()) {
String root = find(parent, email);
groups.computeIfAbsent(root, k -> new TreeSet<>()).add(email);
}
List<List<String>> result = new ArrayList<>();
for (var entry : groups.entrySet()) {
List<String> merged = new ArrayList<>();
merged.add(emailToName.get(entry.getKey()));
merged.addAll(entry.getValue());
result.add(merged);
}
return result;
}
private String find(Map<String, String> parent, String x) {
if (!parent.get(x).equals(x)) parent.put(x, find(parent, parent.get(x)));
return parent.get(x);
}
private void union(Map<String, String> parent, String a, String b) {
parent.putIfAbsent(a, a);
parent.putIfAbsent(b, b);
parent.put(find(parent, a), find(parent, b));
}Time: O(N K log(NK)) — N accounts, K emails each, dominated by the TreeSet sort · Space: O(N K)