medium

Accounts Merge

Merge accounts that share at least one email address into a single account.

1. Define the problem

Accounts Merge

Given a list of accounts, where each account is a list of strings where the first element is a name and the rest are emails, merge accounts that share at least one email address. Two accounts belong to the same person if they share any email, even if the shared email connects them only through a third account. Return the merged accounts, each with its emails sorted . Union accounts whenever an email is seen twice.

Constraints

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

Example

Inputaccounts = [["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"],["John","johnnybravo@mail.com"],["Mary","mary@mail.com"]]

Explanation The first two "John" accounts share johnsmith@mail.com, so they merge. The third "John" account shares no email with them, so it stays separate.

2. Visualize the solution

Union accounts on shared emails, then collect groups

Union accounts on shared emails, then collect groups
Statusunion

Account 1 also lists johnsmith@mail.com — union account 0 and account 1.

What happens in this step

union(1, 0)
find(1) → 1   find(0) → 0
roots differ → union: parent[1] = 0
parent array: [0, 1, 2, 3] → [0, 0, 2, 3]

johnsmith@mail.com was first seen under account 0; account 1 lists it too, so accounts 0 and 1 merge under root 0.
Step 1 of 3

Steps to visualize

  1. Give every account its own group.
  2. Walk every email in every account; if an email was already seen under a different account, union the two accounts.
  3. Once every email has been processed, group emails by their root account.
  4. For each group, sort its emails and pair them with the group's name.
3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Union accounts on shared emails, then collect groups
Statusunion

Account 1 also lists johnsmith@mail.com — union account 0 and account 1.

What happens in this step

union(1, 0)
find(1) → 1   find(0) → 0
roots differ → union: parent[1] = 0
parent array: [0, 1, 2, 3] → [0, 0, 2, 3]

johnsmith@mail.com was first seen under account 0; account 1 lists it too, so accounts 0 and 1 merge under root 0.
Step 1 of 3
4. Solution

Solution

solution.tsTypeScript
function accountsMerge(accounts) {
  const n = accounts.length;
  const parent = Array.from({ length: n }, (_, i) => i);

  function find(x) {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]];
      x = parent[x];
    }
    return x;
  }

  function union(a, b) {
    const rootA = find(a);
    const rootB = find(b);
    if (rootA !== rootB) {
      parent[rootA] = rootB;
    }
  }

  const emailToAccount = new Map();
  for (let i = 0; i < n; i++) {
    for (let j = 1; j < accounts[i].length; j++) {
      const email = accounts[i][j];
      if (emailToAccount.has(email)) {
        union(i, emailToAccount.get(email));
      } else {
        emailToAccount.set(email, i);
      }
    }
  }

  const groups = new Map();
  for (const [email, ownerIndex] of emailToAccount) {
    const root = find(ownerIndex);
    if (!groups.has(root)) groups.set(root, new Set());
    groups.get(root).add(email);
  }

  const result = [];
  for (const [root, emails] of groups) {
    const name = accounts[root][0];
    const sortedEmails = Array.from(emails).sort();
    result.push([name, ...sortedEmails]);
  }

  result.sort((a, b) => {
    const joinedA = a.join(',');
    const joinedB = b.join(',');
    if (joinedA === joinedB) return 0;
    return joinedA < joinedB ? -1 : 1;
  });

  return result;
}
Time
O(n log n)
Space
O(n)
5. Test cases

Test cases

InputExpectedCovers
accounts = [["John","johnsmith@mail.com","john_newyork@mail.com"],["John","johnsmith@mail.com","john00@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]][["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],["John","johnnybravo@mail.com"],["Mary","mary@mail.com"]]example from the docstring
accounts = [["Alice","alice@mail.com"]][["Alice","alice@mail.com"]]smallest valid input, one account with one email
accounts = [["Bob","b1@mail.com"],["Bob","b2@mail.com"]][["Bob","b1@mail.com"],["Bob","b2@mail.com"]]same name but no shared email, accounts stay separate
accounts = [["A","x@mail.com","y@mail.com"],["A","y@mail.com","z@mail.com"],["A","z@mail.com","w@mail.com"]][["A","w@mail.com","x@mail.com","y@mail.com","z@mail.com"]]three accounts chained together through overlapping shared emails
accounts = [["Kevin","k1@mail.com"],["Kevin","k2@mail.com"],["Kevin","k1@mail.com","k3@mail.com"]][["Kevin","k1@mail.com","k3@mail.com"],["Kevin","k2@mail.com"]]one merged group and one separate account sharing the same name

Keep reading