Accounts Merge

You are given a list accounts. Each entry is a list whose first element is a person’s name and whose remaining elements are email addresses belonging to that account.

Two accounts belong to the same person if they have at least one email in common, and this is transitive: if account A shares an email with B, and B shares one with C, then A, B and C are all the same person. Accounts that share the same name but no email (directly or through a chain) may belong to different people and must stay separate. All accounts of one person carry the same name.

Merge the accounts of each person and return one entry per person in the form [name, email1, email2, ...], with that person’s emails listed once each in sorted (lexicographic) order. The people may be returned in any order.

Example 1

Example 2

Example 3

Constraints

• 1 <= accounts.length <= 1000
• 2 <= accounts[i].length <= 10
• Names and emails are non-empty strings of at most 30 characters.
• Accounts sharing an email always have the same name.

Pattern Path · Graphs: Ordering & Union-Find · problem 140 of 169

Start simple

Repeatedly compare every pair of accounts and merge any two that share an email until nothing changes: O(n² · k) per pass with up to n passes.

The key idea

Model the data as a graph whose nodes are email addresses. An account says “all of these emails belong together”, which you can express with just a chain of edges: connect every email of the account to the account’s first email. Two emails belong to the same person exactly when they are connected by some path, so each person is one connected component. That takes care of the transitive A–B–C case automatically.

Union-find is a natural fit. For each account, union(first, e) for every other email e, and record owner[e] = name. With path compression, each operation is close to constant time. Afterwards, group all emails by find(e), sort each group, and prepend the owner’s name.

Notice that names are never used to decide merges, only emails are. Two people called Ana with disjoint emails therefore end up in different components, as required. A DFS or BFS over an adjacency list built the same way works equally well.

Complexity

• Time: O(E log E), E = total number of emails (sorting dominates)
• Space: O(E)

Python

from collections import defaultdict


class Solution:
    def accountsMerge(self, accounts):
        parent = {}

        def find(x):
            # Find the root, compressing the path on the way back.
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        def union(a, b):
            parent[find(a)] = find(b)

        owner = {}
        for name, *emails in accounts:
            for email in emails:
                parent.setdefault(email, email)
                owner[email] = name
                union(email, emails[0])   # every email joins the account's first one

        groups = defaultdict(list)
        for email in parent:
            groups[find(email)].append(email)

        return [[owner[root]] + sorted(emails) for root, emails in groups.items()]

JavaScript

var accountsMerge = function(accounts) {
  const parent = new Map();

  const find = (x) => {
    // Find the root, compressing the path on the way.
    while (parent.get(x) !== x) {
      parent.set(x, parent.get(parent.get(x)));
      x = parent.get(x);
    }
    return x;
  };

  const union = (a, b) => parent.set(find(a), find(b));

  const owner = new Map();
  for (const [name, ...emails] of accounts) {
    for (const email of emails) {
      if (!parent.has(email)) parent.set(email, email);
      owner.set(email, name);
      union(email, emails[0]); // every email joins the account's first one
    }
  }

  const groups = new Map();
  for (const email of parent.keys()) {
    const root = find(email);
    if (!groups.has(root)) groups.set(root, []);
    groups.get(root).push(email);
  }

  const result = [];
  for (const [root, emails] of groups) {
    emails.sort(); // default sort compares strings by code unit, like Python
    result.push([owner.get(root), ...emails]);
  }
  return result;
};

What the interviewer is checking

The interviewer wants you to recognise a hidden connected-components problem in record data, and to choose between union-find and graph traversal with clear reasoning.

Mistakes to avoid

• Merging accounts because they have the same name.
• Only merging accounts that share an email directly, missing chains through a third account.
• Emitting duplicate emails, or forgetting to sort them.

Follow-ups to expect

• Accounts arrive one at a time; keep groups up to date. (Incremental union-find.)
• Also link accounts sharing a phone number. (Add phones as extra nodes.)
• What if the data is too large for one machine? (Distributed connected components.)

In real software

Identity resolution in CRMs and ad platforms, de-duplicating customer records and merging user profiles after sign-ins from several providers all use this connected-components idea.

Practice next