Course4all

Accounts Merge

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Union Find.

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);
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionNumber of Provinces
Next Question →Redundant Connection