Given accounts where each account is [name, email1, email2, ...], merge accounts sharing any email. Return merged accounts sorted.
Input: [["John","j@j.com","j2@j.com"],["John","j3@j.com","j@j.com"],["Mary","m@m.com"]] → Output: [["John","j@j.com","j2@j.com","j3@j.com"],["Mary","m@m.com"]]
Union-Find on email addresses. Map each email to an account index. Union all emails within the same account. Group emails by root and sort.
- Map each email to its first-seen account index.
- Union-Find: for each account, union all its emails with the first email.
- Group emails by their root representative.
- Sort emails in each group and prepend account name.
import java.util.*;
class Solution {
Map<String,String> parent = new HashMap<>();
public List<List<String>> accountsMerge(List<List<String>> accounts) {
// initialize
for (List<String> acc : accounts)
for (int i = 1; i < acc.size(); i++) parent.put(acc.get(i), acc.get(i));
// union emails in same account
Map<String,String> emailToName = new HashMap<>();
for (List<String> acc : accounts) {
String name = acc.get(0), root = find(acc.get(1));
emailToName.put(acc.get(1), name);
for (int i = 2; i < acc.size(); i++) {
emailToName.put(acc.get(i), name);
parent.put(find(acc.get(i)), root);
}
}
// group by root
Map<String,TreeSet<String>> groups = new HashMap<>();
for (String email : parent.keySet())
groups.computeIfAbsent(find(email), k->new TreeSet<>()).add(email);
List<List<String>> res = new ArrayList<>();
for (Map.Entry<String,TreeSet<String>> e : groups.entrySet()) {
List<String> acc = new ArrayList<>();
acc.add(emailToName.get(e.getKey()));
acc.addAll(e.getValue());
res.add(acc);
}
return res;
}
private String find(String x) {
if (!parent.get(x).equals(x)) parent.put(x, find(parent.get(x)));
return parent.get(x);
}
}
- Time Complexity: O(N * E * alpha) where E=emails per account
- Space Complexity: O(N * E)