⬅ Previous Topic
Most Stones Removed with Same Row or ColumnNext Topic ⮕
Number of Islands II - Online Queries using DSU⬅ Previous Topic
Most Stones Removed with Same Row or ColumnNext Topic ⮕
Number of Islands II - Online Queries using DSUTopic Contents
You're given a list of accounts. Each account is a list where the first element is a user name and the rest are email addresses belonging to that person. Your task is to merge the accounts if any two accounts share at least one common email.
Important: Two accounts with the same name are not necessarily the same person unless they share an email. After merging, return each account with the name followed by the sorted list of unique emails.
parent[email] = email
.union(email, first_email)
.email_to_name[email] = account[0]
.find(email)
and group emails by root.function accountsMerge(accounts) {
const parent = {};
const emailToName = {};
function find(x) {
if (parent[x] !== x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
function union(x, y) {
parent[find(x)] = find(y);
}
for (const account of accounts) {
const [name, ...emails] = account;
for (const email of emails) {
if (!parent[email]) parent[email] = email;
emailToName[email] = name;
union(emails[0], email);
}
}
const unions = {};
for (const email of Object.keys(parent)) {
const root = find(email);
if (!unions[root]) unions[root] = [];
unions[root].push(email);
}
const result = [];
for (const emails of Object.values(unions)) {
emails.sort();
result.push([emailToName[emails[0]], ...emails]);
}
return result;
}
console.log(accountsMerge([
["John", "johnsmith@mail.com", "john00@mail.com"],
["John", "johnnybravo@mail.com"],
["John", "johnsmith@mail.com", "john_newyork@mail.com"],
["Mary", "mary@mail.com"]
]));
⬅ Previous Topic
Most Stones Removed with Same Row or ColumnNext Topic ⮕
Number of Islands II - Online Queries using DSUYou can support this website with a contribution of your choice.
When making a contribution, mention your name, and programguru.org in the message. Your name shall be displayed in the sponsors list.