Accounts Merge

union-findgraphhash-map

Problem

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.

Examples

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.

Constraints

•1 <= accounts.length <= 1000
•2 <= accounts[i].length <= 10
•Emails consist of lowercase letters, digits, '+', '.', and '@'

Hints

Hint 1

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.

Hint 2

After unioning, group emails by their root parent — each group is one merged account.

Solutions

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)