Last updated on October 5th, 2024 at 04:26 pm
Here, We see Accounts Merge LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.
List of all LeetCode Solution
Topics
Depth First Search, Union-Find
Companies
Level of Question
Medium
Accounts Merge LeetCode Solution
Table of Contents
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”]]
1. Accounts Merge LeetCode Solution 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;
}
};2. Accounts Merge LeetCode Solution 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. Accounts Merge Leetcode Solution 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()]);
};4. Accounts Merge Leetcode Solution 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