Accounts Merge

Given accounts where each account is [name, email1, email2, ...], merge accounts sharing any email. Return merged accounts sorted.

Example 1

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

Solution Approach

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.

Java

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)