Editorial
Core insight
Accounts Merge · Graph Traversal Patterns (DFS & BFS)
Core Insight for Accounts Merge
The key intuition is to shift our perspective from "merging accounts" to "grouping emails."
- Emails are Nodes: Think of every unique email address as a node in a graph.
- Accounts are Edges: If an account entry looks like
["John", "a@mail.com", "b@mail.com"], this implies thata@mail.comandb@mail.comare connected. They belong to the same component. - Transitivity: If Account 1 has emails
{A, B}and Account 2 has emails{B, C}, the common emailBacts as a bridge.Ais connected toB, andBis connected toC; therefore,A,B, andCare all part of the same connected component.
Visual Description: Imagine a graph where every unique email is a vertex. Iterate through each account. For an account with emails , draw an edge between and . Once we process all accounts, the graph will consist of several isolated clusters (connected components). Each cluster represents one unique person. We can then collect all emails in a cluster and assign them the correct name.
Deep dive
Full breakdown
Full reasoning, pitfalls, and implementation flow
LeetCode 721: Accounts Merge Solution & Explanation
Problem Overview
TL;DR: Treat every email as a node in a graph and use Union-Find (DSU) to group connected components, where an edge exists between any two emails appearing in the same account list.
The LeetCode Accounts Merge problem asks us to consolidate a list of user accounts. Each account consists of a name and a list of emails. The core challenge is that different entries might belong to the same person if they share at least one common email. However, the same name does not guarantee the same identity. Our goal is to merge all accounts belonging to the same individual and return them with emails sorted.
Brute Force Approach for Accounts Merge
A naive approach attempts to build the merged accounts by iteratively comparing every account with every other account.
- Start with the list of accounts.
- Compare
accounts[i]withaccounts[j]. - Check if there is any intersection between their email lists.
- If an intersection exists, merge the two lists of emails and mark them as belonging to the same set.
- Repeat this process until no more merges can be performed (a process similar to bubble sort or fixed-point iteration).
Pseudo-code:
repeat:
merged = false
for i from 0 to N:
for j from i+1 to N:
if accounts[i] and accounts[j] share an email:
accounts[i] = union(accounts[i], accounts[j])
remove accounts[j]
merged = true
until merged is falseWhy it fails: This approach is highly inefficient. Checking for intersections between arbitrary lists takes significant time. Furthermore, the "ripple effect" of merging (where A connects to B, and B connects to C, implying A connects to C) might require many passes through the entire list to propagate. In the worst case, the time complexity approaches , where is the number of accounts and is the max number of emails. This leads to Time Limit Exceeded (TLE) on larger inputs.
Algorithm Strategy: Graph - Union-Find (Disjoint Set Union - DSU)
We will utilize the Union-Find data structure to manage the disjoint sets of emails.
- Initialization: We need a DSU structure capable of handling string keys (emails). We can implement this using a hash map where
parent[email] = parent_email. - Mapping Owners: We also need a map
emailToNameto remember which name is associated with each email. Since all emails in a connected component belong to the same person, we only need to record the name for one email in the component (or all of them; the name is consistent). - Union Operations:
- Iterate through each account in the input list.
- For each account, select the first email as a "pivot".
- Perform a
Unionoperation between the first email and every subsequent email in that account's list. This effectively stitches all emails in that account into a single set.
- Grouping:
- After processing all accounts, iterate through every unique email encountered.
- Find the representative (root) of that email using
Find(email). - Group emails into a list keyed by their representative root.
- Formatting:
- For each group, look up the name using the representative email.
- Sort the emails within the group.
- Construct the final result list.
Execution Flow
Let's trace the algorithm with accounts = [["John", "a@m.com", "b@m.com"], ["John", "b@m.com", "c@m.com"], ["Mary", "d@m.com"]].
- Initialize:
parent = {},emailToName = {}. - Process Account 1
["John", "a@m.com", "b@m.com"]:- Map
a@m.com-> "John",b@m.com-> "John". Union("a@m.com", "b@m.com"). Parent ofbbecomesa.
- Map
- Process Account 2
["John", "b@m.com", "c@m.com"]:- Map
c@m.com-> "John". Union("b@m.com", "c@m.com").Find("b@m.com")leads toa@m.com.Find("c@m.com")isc@m.com.- Parent of
cbecomesa. - Now
a,b, andcare in the same set rooted ata.
- Map
- Process Account 3
["Mary", "d@m.com"]:- Map
d@m.com-> "Mary". - Only one email, no union needed (or union with itself). Root is
d.
- Map
- Build Components:
- Iterate all emails:
a, b, c, d. Find(a) -> a. Groupa:[a]Find(b) -> a. Groupa:[a, b]Find(c) -> a. Groupa:[a, b, c]Find(d) -> d. Groupd:[d]
- Iterate all emails:
- Format Output:
- Group
a: Name is "John". Sort emails:["a@m.com", "b@m.com", "c@m.com"]. Result:["John", "a...", "b...", "c..."]. - Group
d: Name is "Mary". Sort emails:["d@m.com"]. Result:["Mary", "d..."].
- Group
Proof of Correctness
The correctness relies on the properties of the Disjoint Set Union structure.
- Connectivity: The problem defines two accounts as "connected" if they share an email. DSU strictly enforces this: by uniting all emails in a single account, and then uniting emails across accounts via their intersections, we build the transitive closure of the connectivity graph.
- Disjoint Sets: DSU guarantees that after all operations, elements are partitioned into disjoint sets. No email can belong to two different resulting people.
- Invariant: The
emailToNamemapping remains valid because the problem statement guarantees that all accounts belonging to the same person have the same name. Therefore, any email in a connected component can provide the correct name.
Pattern Reuse Notes
The Union-Find (DSU) pattern used in this optimal solution for interviews is highly versatile. It applies to:
- LeetCode 200: Number of Islands (Can be solved with DSU by unioning adjacent land cells).
- LeetCode 261: Graph Valid Tree (DSU detects cycles; a valid tree has no cycles and 1 connected component).
- LeetCode 305: Number of Islands II (Dynamic updates to grid connectivity require DSU for efficiency).
- LeetCode 323: Number of Connected Components in an Undirected Graph (Accounts Merge is essentially this problem, where nodes are emails).
Feynman coach · Before you peek at the code
Can you explain the core insight in your own words?
If you can explain it before reading code, you’re far more likely to recall it under interview pressure.
Loading your attempt…
Reference Implementation
C++ Solution for LeetCode 721
1#include <vector>
2#include <string>
3#include <unordered_map>
4#include <algorithm>
5#include <map>
6
7using namespace std;
8
9class Solution {
10 // DSU Implementation
11 unordered_map<string, string> parent;
12
13 string find(string email) {
14 // Path compression
15 if (parent[email] == email) {
16 return email;
17 }
18 return parent[email] = find(parent[email]);
19 }
20
21 void unionSets(string e1, string e2) {
22 string root1 = find(e1);
23 string root2 = find(e2);
24 if (root1 != root2) {
25 parent[root1] = root2; // Union
26 }
27 }
28
29public:
30 vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
31 unordered_map<string, string> emailToName;
32
33 // 1. Initialize DSU and map emails to names
34 for (const auto& acc : accounts) {
35 string name = acc[0];
36 for (int i = 1; i < acc.size(); ++i) {
37 string email = acc[i];
38 emailToName[email] = name;
39 if (parent.find(email) == parent.end()) {
40 parent[email] = email;
41 }
42
43 // Union current email with the previous one in the list
44 if (i > 1) {
45 unionSets(acc[i], acc[i-1]);
46 }
47 }
48 }
49
50 // 2. Group emails by their root parent
51 unordered_map<string, vector<string>> components;
52 for (auto& pair : parent) {
53 string email = pair.first;
54 string root = find(email);
55 components[root].push_back(email);
56 }
57
58 // 3. Format the result
59 vector<vector<string>> result;
60 for (auto& pair : components) {
61 vector<string> emails = pair.second;
62 sort(emails.begin(), emails.end());
63
64 vector<string> account;
65 account.push_back(emailToName[pair.first]); // Add Name
66 account.insert(account.end(), emails.begin(), emails.end()); // Add Sorted Emails
67 result.push_back(account);
68 }
69
70 return result;
71 }
72};Java Solution for LeetCode 721
1import java.util.*;
2
3class Solution {
4 public List<List<String>> accountsMerge(List<List<String>> accounts) {
5 Map<String, String> parent = new HashMap<>();
6 Map<String, String> emailToName = new HashMap<>();
7
8 // 1. Initialize DSU and perform Unions
9 for (List<String> account : accounts) {
10 String name = account.get(0);
11 for (int i = 1; i < account.size(); i++) {
12 String email = account.get(i);
13 emailToName.put(email, name);
14 parent.putIfAbsent(email, email);
15
16 if (i > 1) {
17 union(parent, account.get(i), account.get(i - 1));
18 }
19 }
20 }
21
22 // 2. Group emails by Root
23 Map<String, List<String>> components = new HashMap<>();
24 for (String email : parent.keySet()) {
25 String root = find(parent, email);
26 components.computeIfAbsent(root, k -> new ArrayList<>()).add(email);
27 }
28
29 // 3. Format Output
30 List<List<String>> result = new ArrayList<>();
31 for (String root : components.keySet()) {
32 List<String> emails = components.get(root);
33 Collections.sort(emails);
34
35 List<String> mergedAccount = new ArrayList<>();
36 mergedAccount.add(emailToName.get(root)); // Add Name
37 mergedAccount.addAll(emails); // Add Emails
38 result.add(mergedAccount);
39 }
40
41 return result;
42 }
43
44 private String find(Map<String, String> parent, String s) {
45 if (!parent.get(s).equals(s)) {
46 parent.put(s, find(parent, parent.get(s))); // Path Compression
47 }
48 return parent.get(s);
49 }
50
51 private void union(Map<String, String> parent, String s1, String s2) {
52 String root1 = find(parent, s1);
53 String root2 = find(parent, s2);
54 if (!root1.equals(root2)) {
55 parent.put(root1, root2);
56 }
57 }
58}Python Solution for LeetCode 721
1class Solution:
2 def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
3 parent = {}
4 email_to_name = {}
5
6 def find(x):
7 if parent[x] != x:
8 parent[x] = find(parent[x]) # Path compression
9 return parent[x]
10
11 def union(x, y):
12 rootX = find(x)
13 rootY = find(y)
14 if rootX != rootY:
15 parent[rootX] = rootY
16
17 # 1. Initialize DSU and Union emails within each account
18 for acc in accounts:
19 name = acc[0]
20 first_email = acc[1]
21 for email in acc[1:]:
22 if email not in parent:
23 parent[email] = email
24 email_to_name[email] = name
25 union(first_email, email)
26
27 # 2. Group emails by their root
28 components = {}
29 for email in parent:
30 root = find(email)
31 if root not in components:
32 components[root] = []
33 components[root].append(email)
34
35 # 3. Format Output
36 result = []
37 for root, emails in components.items():
38 result.append([email_to_name[root]] + sorted(emails))
39
40 return result