Skip to main content

721. Accounts Merge

mediumAsked at Uber

Given a list of accounts, each with a name and emails, merge accounts that share any email. Uber asks this to test Union-Find on email -> account mapping (or DFS on the implicit graph).

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Uber loops.

  • Glassdoor (2026-Q1)— Uber L4/L5 onsite reports include this as a recurring Union-Find medium.
  • Blind (2025-12)— Recurring in Uber identity / fraud team interviews.

Problem

Given a list 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. Two accounts definitely belong to the same person if there is some common email to both accounts. Merge the accounts and return them in the form: the first element of each account is the name, and the rest are emails in sorted order.

Constraints

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

Examples

Example 1

Approaches

1. Build email graph + DFS connected components

For each account, add edges between consecutive emails. DFS to gather connected emails; output sorted with the owner's name.

Time
O(N * K log(N * K))
Space
O(N * K)
function accountsMergeDFS(accounts) {
  const graph = new Map();
  const emailToName = new Map();
  function add(u, v) {
    if (!graph.has(u)) graph.set(u, new Set());
    graph.get(u).add(v);
  }
  for (const acc of accounts) {
    const name = acc[0];
    for (let i = 1; i < acc.length; i++) {
      emailToName.set(acc[i], name);
      if (i > 1) { add(acc[i], acc[i - 1]); add(acc[i - 1], acc[i]); }
      else add(acc[i], acc[i]);
    }
  }
  const seen = new Set();
  const result = [];
  for (const email of graph.keys()) {
    if (seen.has(email)) continue;
    const component = [];
    const stack = [email];
    while (stack.length) {
      const u = stack.pop();
      if (seen.has(u)) continue;
      seen.add(u);
      component.push(u);
      for (const v of graph.get(u) || []) stack.push(v);
    }
    component.sort();
    result.push([emailToName.get(email), ...component]);
  }
  return result;
}

Tradeoff: Direct modeling: emails in the same account are edge-connected. DFS gathers each component. Sorting per component dominates the total cost.

2. Union-Find on email -> root email (optimal)

For each account, union all its emails to the first one. Walk every email, group by root, sort within group.

Time
O(N * K log(N * K))
Space
O(N * K)
function accountsMerge(accounts) {
  const parent = new Map();
  const emailToName = new Map();
  function find(x) {
    if (parent.get(x) !== x) parent.set(x, find(parent.get(x)));
    return parent.get(x);
  }
  for (const acc of accounts) {
    const name = acc[0];
    for (let i = 1; i < acc.length; i++) {
      if (!parent.has(acc[i])) parent.set(acc[i], acc[i]);
      emailToName.set(acc[i], name);
      if (i > 1) parent.set(find(acc[i]), find(acc[i - 1]));
    }
  }
  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();
    result.push([emailToName.get(root), ...emails]);
  }
  return result;
}

Tradeoff: Cleanest answer for this problem. Union-Find handles the 'two accounts share an email' transitivity in near-linear time. Sorting per group dominates.

Uber-specific tips

Uber wants the framing said out loud: 'Two accounts sharing any email belong to the same person. That's a connected-components problem on the email graph.' Then choose your tool — Union-Find is the cleaner whiteboard answer here. Skipping the framing and just writing DFS code is a flag at L5.

Common mistakes

  • Building an account-to-account graph (size N^2 in the worst case) instead of an email-to-email graph (size sum of emails).
  • Forgetting to sort the emails within each merged account.
  • Putting the name as the first element by reading it from emailToName but using the wrong representative email.

Follow-up questions

An interviewer at Uber may pivot to one of these next:

  • Number of Provinces (LC 547) — same connected-components pattern on a different domain.
  • Friend Circles or social graph — apply this idea to user relationships.
  • What if two people had the same name and shared no emails? (They stay separate — the problem is by email overlap, not name.)

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why Union-Find over DFS here?

Both work. Union-Find is often cleaner for 'merge sets that touch' problems because it sidesteps building an explicit graph. DFS is fine but requires the adjacency list explicitly.

Why does the name need to be stored per-email?

All emails within an account share the name, but you need to recover it from the connected component. Storing email -> name is the simplest way; pick any email from the component to look it up.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Accounts Merge and other Uber interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →