Course4all
Join us on telegram
Home/dsa/Union Find/Accounts Merge

Accounts Merge

Master this topic with zero to advance depth.

Accounts Merge

Given a list of accounts where each element accounts[i] is a list of strings, the first element accounts[i][0] is a name, and the rest are emails. Merge accounts belonging to the same person. Two accounts belong to the same person if there is some common email to both accounts.

Medium

Examples

Input: accounts = [["John","a@m.com","b@m.com"],["John","c@m.com","a@m.com"],["Mary","d@m.com"]]
Output: [["John","a@m.com","b@m.com","c@m.com"],["Mary","d@m.com"]]
Approach 1

Level I: DFS (Graph of Emails)

Intuition

Build an adjacency list where each email is a node and edges connect emails within the same account. Use DFS to find connected components of emails.

⏱ O(N \cdot K \log(N \cdot K))💾 O(N \cdot K)

Detailed Dry Run

Account 1: {a, b}. Account 2: {c, a}. Graph: a-b, c-a. Component: {a, b, c}. Sort and add name 'John'.

java
import java.util.*;
class Solution {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        Map<String, List<String>> adj = 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);
                emailToName.put(email, name);
                if (i > 1) {
                    adj.computeIfAbsent(acc.get(1), k -> new ArrayList<>()).add(email);
                    adj.computeIfAbsent(email, k -> new ArrayList<>()).add(acc.get(1));
                }
            }
        }
        Set<String> visited = new HashSet<>();
        List<List<String>> res = new ArrayList<>();
        for (String email : emailToName.keySet()) {
            if (visited.add(email)) {
                List<String> comp = new ArrayList<>();
                dfs(adj, visited, email, comp);
                Collections.sort(comp);
                comp.add(0, emailToName.get(email));
                res.add(comp);
            }
        }
        return res;
    }
    private void dfs(Map<String, List<String>> adj, Set<String> vis, String u, List<String> comp) {
        comp.add(u);
        if (adj.containsKey(u)) for (String v : adj.get(u)) if (vis.add(v)) dfs(adj, vis, v, comp);
    }
}
Approach 2

Level III: Union-Find (Email Mapping)

Intuition

Use DSU to union all emails within an account. After processing all accounts, group emails by their root parent, sort them, and format the output.

⏱ O(N \cdot K \cdot \alpha(N \cdot K))💾 O(N \cdot K)

Detailed Dry Run

Initial: {a:a, b:b, c:c}. Account 1: Union(a, b) -> {a:b, b:b}. Account 2: Union(c, a) -> {c:b, a:b}. All point to 'b'.

java
import java.util.*;
class Solution {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        Map<String, String> parent = new HashMap<>(), nameMap = new HashMap<>();
        for (List<String> acc : accounts) {
            String rootEmail = acc.get(1);
            for (int i = 1; i < acc.size(); i++) {
                String email = acc.get(i);
                parent.putIfAbsent(email, email);
                nameMap.put(email, acc.get(0));
                union(parent, rootEmail, email);
            }
        }
        Map<String, List<String>> unions = new HashMap<>();
        for (String email : parent.keySet()) {
            String root = find(parent, email);
            unions.computeIfAbsent(root, k -> new ArrayList<>()).add(email);
        }
        List<List<String>> res = new ArrayList<>();
        for (String root : unions.keySet()) {
            List<String> emails = unions.get(root);
            Collections.sort(emails);
            emails.add(0, nameMap.get(root));
            res.add(emails);
        }
        return res;
    }
    private String find(Map<String, String> p, String s) { return p.get(s).equals(s) ? s : p.put(s, find(p, p.get(s))); }
    private void union(Map<String, String> p, String a, String b) {
        String r1 = find(p, a), r2 = find(p, b); if(!r1.equals(r2)) p.put(r1, r2);
    }
}
← Previous QuestionNumber of Provinces
Next Question →Redundant Connection