Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumunion-find

Accounts Merge

Problem (restated)

Each account is [name, email…]. Merge accounts that share any email. Output [name, sorted unique emails…]. Same name alone does not merge.

Intuition

Treat each account index as a UF node. Map email → first account id; union when email already seen.

Approaches

Union accounts sharing emails

Unverified

Time O(N α(N) + E log E)Space O(N + E)

Idea. After unions, group emails by root; sort each group; prepend the root account’s name.

Walkthrough. Two John accounts sharing johnsmith@mail.com collapse into one sorted email list.

Trade-offs. Graph BFS on email graph is equivalent; UF is compact.

Solution

export function accountsMerge(accounts: string[][]): string[][] {
  const n = accounts.length;
  const parent = Array.from({ length: n }, (_, i) => i);
  const find = (x: number): number => {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]!]!;
      x = parent[x]!;
    }
    return x;
  };
  const union = (a: number, b: number) => {
    const ra = find(a), rb = find(b);
    if (ra !== rb) parent[rb] = ra;
  };
  const emailToId = new Map<string, number>();
  for (let i = 0; i < n; i++) {
    for (let j = 1; j < accounts[i]!.length; j++) {
      const email = accounts[i]![j]!;
      if (emailToId.has(email)) union(emailToId.get(email)!, i);
      else emailToId.set(email, i);
    }
  }
  const groups = new Map<number, Set<string>>();
  for (let i = 0; i < n; i++) {
    const r = find(i);
    if (!groups.has(r)) groups.set(r, new Set());
    for (let j = 1; j < accounts[i]!.length; j++) groups.get(r)!.add(accounts[i]![j]!);
  }
  const res: string[][] = [];
  for (const [r, emails] of groups) {
    res.push([accounts[r]![0]!, ...[...emails].sort()]);
  }
  return res;
}

export function accountsMerge(accounts: string[][]): string[][] {
  const n = accounts.length;
  const parent = Array.from({ length: n }, (_, i) => i);
  const find = (x: number): number => {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]!]!;
      x = parent[x]!;
    }
    return x;
  };
  const union = (a: number, b: number) => {
    const ra = find(a), rb = find(b);
    if (ra !== rb) parent[rb] = ra;
  };
  const emailToId = new Map<string, number>();
  for (let i = 0; i < n; i++) {
    for (let j = 1; j < accounts[i]!.length; j++) {
      const email = accounts[i]![j]!;
      if (emailToId.has(email)) union(emailToId.get(email)!, i);
      else emailToId.set(email, i);
    }
  }
  const groups = new Map<number, Set<string>>();
  for (let i = 0; i < n; i++) {
    const r = find(i);
    if (!groups.has(r)) groups.set(r, new Set());
    for (let j = 1; j < accounts[i]!.length; j++) groups.get(r)!.add(accounts[i]![j]!);
  }
  const res: string[][] = [];
  for (const [r, emails] of groups) {
    res.push([accounts[r]![0]!, ...[...emails].sort()]);
  }
  return res;
}

Template connection

Union-Find over equivalence classes (shared keys).

Reflection

Accounts that share an email are unioned. The name stays on the first account that was seen. Emails are written in sorted order.
The same name with no shared email is two people. The name is not the key.
One account returns its emails sorted. An account with no emails still returns a row that holds only the name.