Accounts Merge Using Graphs and DSU

Problem Statement❯

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.

Examples❯

Input Accounts	Merged Output	Description
[ ["John", "johnsmith@mail.com", "john00@mail.com"], ["John", "johnnybravo@mail.com"], ["John", "johnsmith@mail.com", "john_newyork@mail.com"], ["Mary", "mary@mail.com"] ]	[ ["John", "john00@mail.com", "john_newyork@mail.com", "johnsmith@mail.com"], ["John", "johnnybravo@mail.com"], ["Mary", "mary@mail.com"] ]	First and third John accounts are merged via common email
[ ["Alex", "a@mail.com"], ["Alex", "b@mail.com"], ["Alex", "a@mail.com", "b@mail.com"] ]	[ ["Alex", "a@mail.com", "b@mail.com"] ]	All Alex accounts are connected through emails
[]	[]	No accounts to process
[ ["Bob", "bob@mail.com"] ]	[ ["Bob", "bob@mail.com"] ]	Single account, no merging needed

Solution❯

This problem can be visualized as a graph where each email is a node, and if two emails appear in the same account, there's an edge between them. All emails connected in such a way belong to the same person.

We use Disjoint Set Union (DSU) to group connected emails efficiently. Here’s the approach:

Iterate over all accounts and connect all emails in the same account using DSU (union operation).
Map each email to the corresponding user name.
Traverse all emails, find their root parent, and group them accordingly.
For each group, sort the emails and prepend the user name.

DSU helps efficiently manage merging and finding connected components (email clusters).

Algorithm Steps❯

Initialize a parent map for DSU: parent[email] = email.
Iterate through each account:

For each email in the account, perform union(email, first_email).
Record email_to_name[email] = account[0].

For each email, find its root parent using find(email) and group emails by root.
For each group, sort the emails and prepend the name.
Return the list of merged accounts.

Code

JavaScript

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 TopicMost Stones Removed with Same Row or Column

Next Topic ⮕Number of Islands II - Online Queries using DSU