Back to DSA

Accounts Merge

medium
Acceptance: 49%
GraphsUnion FindDFS

You have a list of user accounts. Each account starts with a user name followed by one or more email addresses. Two accounts belong to the same person if they share at least one email. Merge all accounts belonging to the same person. Return the merged accounts with the name first and remaining emails sorted alphabetically.

Examples

Example 1:
Input:accounts = [["Alice","a1@mail.com","a2@mail.com"],["Alice","a2@mail.com","a3@mail.com"],["Bob","b1@mail.com"]]
Output:[["Alice","a1@mail.com","a2@mail.com","a3@mail.com"],["Bob","b1@mail.com"]]
Explanation: The two Alice accounts share a2@mail.com and are merged.

Hints

Related Problems

Clone GraphmediumPacific Atlantic Water FlowmediumRotting OrangesmediumWalls and GatesmediumShortest Path in Binary Matrixmedium
00:00
import java.util.*;

class Solution {
    private int[] parent;

    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));
                else emailToId.put(email, i);
            }
        }
        Map<Integer, TreeSet<String>> merged = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int root = find(i);
            merged.computeIfAbsent(root, k -> new TreeSet<>());
            for (int j = 1; j < accounts.get(i).size(); j++)
                merged.get(root).add(accounts.get(i).get(j));
        }
        List<List<String>> result = new ArrayList<>();
        for (var entry : merged.entrySet()) {
            List<String> list = new ArrayList<>();
            list.add(accounts.get(entry.getKey()).get(0));
            list.addAll(entry.getValue());
            result.add(list);
        }
        return result;
    }

    private int find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }
    private void union(int a, int b) { parent[find(a)] = find(b); }
}
Time complexityO(N * K * alpha(N) + N * K * log(N * K))
Space complexityO(N * K)