Last updated on February 20th, 2025 at 09:25 am
Here, we see an Accounts Merge LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Depth First Search, Union-Find
Companies
Level of Question
Medium
Accounts Merge LeetCode Solution
Table of Contents
1. 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.
Example 1:
Input: accounts = [[“John”,”johnsmith@mail.com”,”john_newyork@mail.com”],[“John”,”johnsmith@mail.com”,”john00@mail.com”],[“Mary”,”mary@mail.com”],[“John”,”johnnybravo@mail.com”]]
Output: [[“John”,”john00@mail.com”,”john_newyork@mail.com”,”johnsmith@mail.com”],[“Mary”,”mary@mail.com”],[“John”,”johnnybravo@anuj_singhExplanation: The first and second John’s are the same person as they have the common email “johnsmith@mail.com”. The third John and Mary are different people as none of their email addresses are used by other accounts. We could return these lists in any order, for example the answer [[‘Mary’, ‘mary@mail.com’], [‘John’, ‘johnnybravo@mail.com’], [‘John’, ‘john00@mail.com’, ‘john_newyork@mail.com’, ‘johnsmith@mail.com’]] would still be accepted.
Example 2:
Input: accounts = [[“Gabe”,”Gabe0@m.co”,”Gabe3@m.co”,”Gabe1@m.co”],[“Kevin”,”Kevin3@m.co”,”Kevin5@m.co”,”Kevin0@m.co”],[“Ethan”,”Ethan5@m.co”,”Ethan4@m.co”,”Ethan0@m.co”],[“Hanzo”,”Hanzo3@m.co”,”Hanzo1@m.co”,”Hanzo0@m.co”],[“Fern”,”Fern5@m.co”,”Fern1@m.co”,”Fern0@m.co”]]
Output: [[“Ethan”,”Ethan0@m.co”,”Ethan4@m.co”,”Ethan5@m.co”],[“Gabe”,”Gabe0@m.co”,”Gabe1@m.co”,”Gabe3@m.co”],[“Hanzo”,”Hanzo0@m.co”,”Hanzo1@m.co”,”Hanzo3@m.co”],[“Kevin”,”Kevin0@m.co”,”Kevin3@m.co”,”Kevin5@m.co”],[“Fern”,”Fern0@m.co”,”Fern1@m.co”,”Fern5@m.co”]]
2. Coding Pattern Used in Solution
The coding pattern used in all the provided implementations is Union-Find (Disjoint Set Union). This pattern is commonly used to solve problems involving grouping or merging connected components, such as finding connected components in a graph or merging accounts with common emails.
3. Code Implementation in Different Languages
3.1 Accounts Merge C++
class Solution {
public:
int find(int node,vector<int>&parent) {
while(parent[node] != node) {
node = parent[node];
}
return node;
}
void unify(int i, int j,vector<int>&parent) {
int iRoot = find(i,parent);
int jRoot = find(j,parent);
if(iRoot != jRoot) {
parent[jRoot] = iRoot;
}
}
vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
int n=accounts.size();
vector<int>parent(n);
for(int i=0;i<n;i++)
parent[i]=i;
map<string,int>mp;
for(int i=0;i<n;i++)
{
for(int j=1;j<accounts[i].size();j++)
{
if(mp.find(accounts[i][j])==mp.end())
{
mp[accounts[i][j]]=i;
}
else
{
unify(mp[accounts[i][j]],i,parent);
}
}
}
int cnt=0;
for(int i=0;i<n;i++)
{
if(parent[i]==i)
cnt++;
}
vector<vector<string>>ans(cnt,vector<string>());
int newidx=0;
map<int,int>mp1;
for(auto &e:mp)
{
string mail=e.first;
int index=e.second;
int grouphead=find(index,parent);
if(mp1.find(grouphead)==mp1.end())
{
mp1[grouphead]=newidx;
ans[newidx].push_back(accounts[grouphead][0]);
ans[newidx].push_back(mail);
newidx++;
}
else
{
int putindex=mp1[grouphead];
ans[putindex].push_back(mail);
}
}
for(int i=0;i<ans.size();i++)
{
sort(ans[i].begin()+1,ans[i].end());
}
return ans;
}
};
3.2 Accounts Merge Java
class Solution {
class UnionFind {
int[] parent;
int[] weight;
public UnionFind(int num) {
parent = new int[num];
weight = new int[num];
for(int i = 0; i < num; i++) {
parent[i] = i;
weight[i] = 1;
}
}
public void union(int a, int b) {
int rootA = root(a);
int rootB = root(b);
if (rootA == rootB) {
return;
}
if (weight[rootA] > weight[rootB]) {
parent[rootB] = rootA;
weight[rootA] += weight[rootB];
} else {
parent[rootA] = rootB;
weight[rootB] += weight[rootA];
}
}
public int root(int a) {
if (parent[a] == a) {
return a;
}
parent[a] = root(parent[a]);
return parent[a];
}
}
public List<List<String>> accountsMerge(List<List<String>> accounts) {
int size = accounts.size();
UnionFind uf = new UnionFind(size);
HashMap<String, Integer> emailToId = new HashMap<>();
for(int i = 0; i < size; i++) {
List<String> details = accounts.get(i);
for(int j = 1; j < details.size(); j++) {
String email = details.get(j);
if (emailToId.containsKey(email)) {
uf.union(i, emailToId.get(email));
} else {
emailToId.put(email, i);
}
}
}
HashMap<Integer, List<String>> idToEmails = new HashMap<>();
for(String key : emailToId.keySet()) {
int root = uf.root(emailToId.get(key));
if (!idToEmails.containsKey(root)) {
idToEmails.put(root, new ArrayList<String>());
}
idToEmails.get(root).add(key);
}
List<List<String>> mergedDetails = new ArrayList<>();
for(Integer id : idToEmails.keySet()) {
List<String> emails = idToEmails.get(id);
Collections.sort(emails);
emails.add(0, accounts.get(id).get(0));
mergedDetails.add(emails);
}
return mergedDetails;
}
}
3.3 Accounts Merge JavaScript
var accountsMerge = function (accounts) {
const parents = {};
const email2name = {};
const find = (x) => {
if (parents[x] !== x) {
parents[x] = find(parents[x]);
}
return parents[x];
};
const union = (x, y) => {
parents[find(x)] = find(y);
};
for (const [name, ...emails] of accounts) {
for (const email of emails) {
if (!parents[email]) {
parents[email] = email;
}
email2name[email] = name;
union(email, emails[0]);
}
}
const emails = {};
for (const email of Object.keys(parents)) {
const parent = find(email);
if (parent in emails) {
emails[parent].push(email);
} else {
emails[parent] = [email];
}
}
return Object.entries(emails).map(([email, x]) => [email2name[email], ...x.sort()]);
};
3.4 Accounts Merge Python
class Solution(object):
def accountsMerge(self, accounts):
em_to_name = {}
em_graph = defaultdict(set)
for acc in accounts:
name = acc[0]
for email in acc[1:]:
em_graph[acc[1]].add(email)
em_graph[email].add(acc[1])
em_to_name[email] = name
seen = set()
ans = []
for email in em_graph:
if email not in seen:
seen.add(email)
st = [email]
component = []
while st:
edge = st.pop()
component.append(edge)
for nei in em_graph[edge]:
if nei not in seen:
seen.add(nei)
st.append(nei)
ans.append([em_to_name[email]] + sorted(component))
return ans
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(N * α(N) + M log M) | O(N + M) |
| Java | O(N * α(N) + M log M) | O(N + M) |
| JavaScript | O(N * α(N) + M log M) | O(N + M) |
| Python | O(N + M log M) | O(N + M) |
Here,
- M = total number of emails
O(N)for building the graphO(N * α(N))for Union-Find operationsα(N)is the inverse Ackermann functionO(M log M)for sorting emails
- Union-Find Efficiency: The Union-Find operations (
findandunion) are very efficient due to path compression and union by rank/weight, making their time complexity nearly constant (O(α(N))). - Sorting Emails: Sorting the emails in each group contributes the
O(M log M)term, whereMis the total number of emails. - Graph Traversal in Python: The Python implementation uses a graph-based approach with DFS instead of Union-Find, but the overall complexity remains similar.
- The code efficiently merges accounts using the Union-Find pattern (or graph traversal in Python) and constructs the result by grouping and sorting emails.
- The time complexity is dominated by the sorting step, while the space complexity is determined by the data structures used for Union-Find or graph representation.