289. Accounts Merge

Map each email to an account index. If the same email appears in two accounts, union them. Then group emails by their root account.

Approach

1. Map each email to account index.
2. If email seen before, union current account with previous.
3. Group all emails by root parent.
4. Sort emails in each group and prepend the account name.

Complexity

• Time: O(n * k * alpha(n)) where k = avg emails per account
• Space: O(n * k)

import java.util.*;

class Solution {
    private int[] parent;

    private int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    private void union(int x, int y) {
        int px = find(x), py = find(y);
        if (px != py) {
            parent[px] = py;
        }
    }

    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        int n = accounts.size();
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;

        Map<String, Integer> emailToId = new HashMap<>();
        for (int i = 0; i < n; i++) {
            for (int j = 1; j < accounts.get(i).size(); j++) {
                String email = accounts.get(i).get(j);
                if (emailToId.containsKey(email)) {
                    union(i, emailToId.get(email));
                }
                emailToId.put(email, i);
            }
        }

        Map<Integer, Set<String>> groups = new HashMap<>();
        for (Map.Entry<String, Integer> entry : emailToId.entrySet()) {
            int root = find(entry.getValue());
            groups.computeIfAbsent(root, k -> new TreeSet<>()).add(entry.getKey());
        }

        List<List<String>> result = new ArrayList<>();
        for (Map.Entry<Integer, Set<String>> entry : groups.entrySet()) {
            List<String> merged = new ArrayList<>();
            merged.add(accounts.get(entry.getKey()).get(0));
            merged.addAll(entry.getValue());
            result.add(merged);
        }

        return result;
    }
}