Log inSign up
mediumLeetCodeNot Started

Accounts Merge

Given a list of accounts where each element accounts[i] is a list of strings, where the first element accounts[i][0] is a name, and the rest of the elements are emails representing emails of the account. Merge accounts that belong to the same person.

Graph
Solve on LeetCode
Lesson

Problem Statement

Given a list of accounts where each element accounts[i] is a list of strings, where the first element accounts[i][0] is a name, and the rest of the elements are emails representing emails of the account.

Now, we would like to merge these accounts. Two accounts definitely belong to the same person if there is some common email to both accounts. Note that even if two accounts have the same name, they may belong to different people as people could have the same name. A person can have any number of accounts initially, but all of their accounts definitely have the same name.

After merging the accounts, return the accounts in the following format: the first element of each account is the name, and the rest of the elements are emails in sorted order. The accounts themselves can be returned in any order.

Constraints:

  • 1 <= accounts.length <= 1000
  • 2 <= accounts[i].length <= 10
  • 1 <= accounts[i][j].length <= 30
  • accounts[i][0] consists of English letters.
  • accounts[i][j] (for j > 0) is a valid email.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand how to model transitive equivalence relationships using graph connectivity and DSU.
  • Implement Disjoint Set Union with path compression and union by rank on string identifiers.
  • Execute account grouping and lexicographical sorting efficiently across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Transitive equivalence grouping ('if A and B share an email, and B and C share an email, then A, B, and C are the same person').
  • Multiple records that must be merged based on shared attributes.
  • Need to return connected components with distinct properties.

Algorithmic Decision Tree:

  • BRUTE FORCE: Iteratively pairwise compare accounts and merge intersecting sets until convergence -> O(N2 * K2) slow.
  • BETTER: Build an undirected adjacency list between emails, then run standard DFS/BFS to collect connected components -> O(N * K * log(N * K)).
  • OPTIMAL: Disjoint Set Union by rank/size indexing each account. Map each email to account index, union intersecting accounts, then gather emails by find() root -> clean O(N * K * α(N) + N * K * log(K)).

Connected Patterns:

Connected ComponentsNumber of ProvincesRedundant Connection

1. Iterative Pairwise Merging

Intuition

Iteratively compare pairs of accounts. If two accounts share at least one email, merge their emails into one account and remove the other. Repeat until a full pass makes zero merges.

Algorithm

  1. Convert each account's emails into a set.
  2. Loop with a merged flag: for every pair (i, j), check if their email sets have a non-empty intersection.
  3. If they intersect, union account j's emails into account i, remove account j, and set merged = true.
  4. Repeat until a complete pass occurs without any merges.
  5. Sort the emails for each merged account and attach the name.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_set>
5#include <algorithm>
6
7using namespace std;
8
9class Solution {
10public:
11 vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
12 vector<pair<string, unordered_set<string>>> accList;
13 for (const auto& acc : accounts) {
14 unordered_set<string> emails(acc.begin() + 1, acc.end());
15 accList.push_back({acc[0], emails});
16 }
17
18 bool merged = true;
19 while (merged) {
20 merged = false;
21 for (size_t i = 0; i < accList.size(); ++i) {
22 for (size_t j = i + 1; j < accList.size(); ++j) {
23 if (accList[i].first != accList[j].first) continue;
24 bool overlap = false;
25 for (const auto& email : accList[j].second) {
26 if (accList[i].second.count(email)) {
27 overlap = true;
28 break;
29 }
30 }
31 if (overlap) {
32 accList[i].second.insert(accList[j].second.begin(), accList[j].second.end());
33 accList.erase(accList.begin() + j);
34 merged = true;
35 break;
36 }
37 }
38 if (merged) break;
39 }
40 }
41
42 vector<vector<string>> result;
43 for (auto& p : accList) {
44 vector<string> emails(p.second.begin(), p.second.end());
45 sort(emails.begin(), emails.end());
46 emails.insert(emails.begin(), p.first);
47 result.push_back(emails);
48 }
49 return result;
50 }
51};
52
53int main() {
54 Solution solver;
55 vector<vector<string>> accounts = {
56 {"John","johnsmith@mail.com","john_newyork@mail.com"},
57 {"John","johnsmith@mail.com","john00@mail.com"},
58 {"Mary","mary@mail.com"},
59 {"John","johnnybravo@mail.com"}
60 };
61 auto res = solver.accountsMerge(accounts);
62 for (const auto& acc : res) {
63 cout << acc[0] << ": ";
64 for (size_t i = 1; i < acc.size(); ++i) cout << acc[i] << " ";
65 cout << endl;
66 }
67 return 0;
68}

Time & Space Complexity

  • Time complexity: O(N^2 * K^2)
  • Space complexity: O(N * K)

2. Graph Adjacency List + DFS

Intuition

Build an undirected graph where nodes are emails and bidirectional edges connect all emails within each account to the first email. Traverse each connected component using DFS.

Algorithm

  1. Create an adjacency list adj (email -> list of emails) and a map emailToName (email -> account owner name).
  2. For each account, connect the first email acc[1] with all other emails acc[i] bidirectionally.
  3. Maintain a visited set of emails.
  4. Iterate through all unique emails in adj. If an email is unvisited, start a DFS to collect all reachable emails in its component.
  5. Sort the collected emails, prepend the owner's name, and add to results.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_map>
5#include <unordered_set>
6#include <algorithm>
7
8using namespace std;
9
10class Solution {
11public:
12 void dfs(const string& email, unordered_map<string, vector<string>>& adj,
13 unordered_set<string>& visited, vector<string>& component) {
14 visited.insert(email);
15 component.push_back(email);
16 for (const string& neighbor : adj[email]) {
17 if (!visited.count(neighbor)) {
18 dfs(neighbor, adj, visited, component);
19 }
20 }
21 }
22
23 vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
24 unordered_map<string, vector<string>> adj;
25 unordered_map<string, string> emailToName;
26
27 for (const auto& acc : accounts) {
28 const string& name = acc[0];
29 const string& firstEmail = acc[1];
30 for (size_t i = 1; i < acc.size(); ++i) {
31 adj[firstEmail].push_back(acc[i]);
32 adj[acc[i]].push_back(firstEmail);
33 emailToName[acc[i]] = name;
34 }
35 }
36
37 unordered_set<string> visited;
38 vector<vector<string>> result;
39
40 for (const auto& pair : adj) {
41 const string& email = pair.first;
42 if (!visited.count(email)) {
43 vector<string> component;
44 dfs(email, adj, visited, component);
45 sort(component.begin(), component.end());
46 component.insert(component.begin(), emailToName[email]);
47 result.push_back(component);
48 }
49 }
50 return result;
51 }
52};
53
54int main() {
55 Solution solver;
56 vector<vector<string>> accounts = {
57 {"John","johnsmith@mail.com","john_newyork@mail.com"},
58 {"John","johnsmith@mail.com","john00@mail.com"},
59 {"Mary","mary@mail.com"},
60 {"John","johnnybravo@mail.com"}
61 };
62 auto res = solver.accountsMerge(accounts);
63 for (const auto& acc : res) {
64 cout << acc[0] << ": ";
65 for (size_t i = 1; i < acc.size(); ++i) cout << acc[i] << " ";
66 cout << endl;
67 }
68 return 0;
69}

Time & Space Complexity

  • Time complexity: O(N * K * log(N * K))
  • Space complexity: O(N * K)

3. Disjoint Set Union (DSU) on Account Indices

Intuition

Map each unique email to the index of the first account that contains it. When an email appears in a subsequent account, union the two account indices using DSU with path compression and rank.

Algorithm

  1. Initialize DSU of size N (one set per account index).
  2. Maintain a map emailToAcc (string -> int).
  3. For each account i, iterate through its emails. If email is seen before in account j, call dsu.union(i, j). Otherwise, register emailToAcc[email] = i.
  4. Group emails by finding their representative: root = dsu.find(emailToAcc[email]), and insert email into grouped[root].
  5. For each group at root, sort the emails, prepend accounts[root][0], and add to final output.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_map>
5#include <numeric>
6#include <algorithm>
7
8using namespace std;
9
10class DSU {
11public:
12 vector<int> parent, rank;
13 DSU(int n) : parent(n), rank(n, 0) {
14 iota(parent.begin(), parent.end(), 0);
15 }
16 int find(int x) {
17 if (parent[x] != x) parent[x] = find(parent[x]);
18 return parent[x];
19 }
20 void unite(int x, int y) {
21 int rootX = find(x), rootY = find(y);
22 if (rootX != rootY) {
23 if (rank[rootX] < rank[rootY]) swap(rootX, rootY);
24 parent[rootY] = rootX;
25 if (rank[rootX] == rank[rootY]) rank[rootX]++;
26 }
27 }
28};
29
30class Solution {
31public:
32 vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
33 int n = accounts.size();
34 DSU dsu(n);
35 unordered_map<string, int> emailToAcc;
36
37 for (int i = 0; i < n; ++i) {
38 for (size_t j = 1; j < accounts[i].size(); ++j) {
39 const string& email = accounts[i][j];
40 if (emailToAcc.count(email)) {
41 dsu.unite(i, emailToAcc[email]);
42 } else {
43 emailToAcc[email] = i;
44 }
45 }
46 }
47
48 unordered_map<int, vector<string>> mergedEmails;
49 for (const auto& pair : emailToAcc) {
50 const string& email = pair.first;
51 int root = dsu.find(pair.second);
52 mergedEmails[root].push_back(email);
53 }
54
55 vector<vector<string>> result;
56 for (auto& pair : mergedEmails) {
57 int root = pair.first;
58 vector<string>& emails = pair.second;
59 sort(emails.begin(), emails.end());
60 emails.insert(emails.begin(), accounts[root][0]);
61 result.push_back(move(emails));
62 }
63 return result;
64 }
65};
66
67int main() {
68 Solution solver;
69 vector<vector<string>> accounts = {
70 {"John","johnsmith@mail.com","john_newyork@mail.com"},
71 {"John","johnsmith@mail.com","john00@mail.com"},
72 {"Mary","mary@mail.com"},
73 {"John","johnnybravo@mail.com"}
74 };
75 auto res = solver.accountsMerge(accounts);
76 for (const auto& acc : res) {
77 cout << acc[0] << ": ";
78 for (size_t i = 1; i < acc.size(); ++i) cout << acc[i] << " ";
79 cout << endl;
80 }
81 return 0;
82}

Time & Space Complexity

  • Time complexity: O(N * K * α(N) + E log E)
  • Space complexity: O(N * K)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Iterative Pairwise Set MergingO(N^2 * K^2)O(N * K)Repeatedly scan all account pairs. If two accounts share an email, merge their sets and delete one account. Repeat until no merges occur.Repeated set intersections across N accounts.
2.Adjacency List + DFS TraversalO(N * K * log(N * K))O(N * K)Build an undirected graph where nodes are emails and edges connect emails appearing in the same account. Run DFS from unvisited emails to gather connected components.Graph construction and sorting collected emails.
3.Disjoint Set Union (DSU) on Account IndicesOptimalO(N * K * α(N) + E log E)O(N * K)Assign each account an index 0 to N-1. Use a hash map emailToAcc to map each email to the first account index that introduced it. If seen again, union the two account indices. Group emails under find(accountIdx) and sort.Final lexicographical sort of emails per merged account.

Common Pitfalls & Crucial Edge Cases

Grouping by account name rather than email connectivity

Causes unrelated individuals with the same name to be merged.

Forgetting to sort emails lexicographically before returning

Violates the explicit output format requirement.

Duplicate emails in final account list

Must ensure emails within each merged component are unique before sorting.

Crucial Edge Cases to Validate:

  • Two different people with identical names and no shared emails — Must remain as separate accounts in the output.
  • Single account with duplicate emails — Must de-duplicate emails and return them sorted.
  • Chained overlap (e.g., Acc1 shares with Acc2, Acc2 shares with Acc3) — All three accounts must be merged into one single component.
  • All accounts disjoint — Returns N accounts with their emails sorted.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clarify whether names can be identical for different users early in the interview to show attention to requirements.
  2. Explain the two valid optimal paradigms: DFS on an email graph vs. DSU on account indices, highlighting why DSU on indices is more memory efficient.
  3. Mention that α(N) is the Inverse Ackermann function, which is effectively constant (<= 4) for all practical values of N.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why can't we simply merge accounts whenever they share the exact same name?

2.What is the primary advantage of running DSU on account indices rather than on email strings directly?

3.What is the time complexity bottleneck in the optimal DSU solution?

Back to DSA Sheet