Typorithm · medium

Accounts Merge

accounts-mergeunion-findemail-mapgroup-by-rootapplication

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn Accounts Merge

Union-Find

Union accounts that share any email via an email→owner map, then group every email by its root and emit name plus sorted emails.

Accounts belong together if they share at least one email, a transitive relation perfect for union-find.

Map each email to the first account that owns it; a repeat email unions the two accounts.

Finally group all emails by their account's root, sort each group, and prepend the owner's name.

Union accounts sharing an email.

Group emails by DSU root.

Sort emails, prepend the name.

function accountsMerge(accounts) {
  const uf = new UnionFind(accounts.length);
  const emailToId = new Map();

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

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

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

  return result;
}

Read the implementation

Connect each part of the code to the concept before you type.

1. Email owner

Map each email to the first account that claimed it.

const emailToId = new Map()

2. Merge on shared email

Two accounts sharing an email belong together.

uf.union(i, emailToId.get(email))

3. Group by root

All emails under one root form a single merged account.

const root = uf.find(id)

4. Name + sorted emails

Prepend the owner's name to the sorted emails.

result.push([accounts[root][0], ...emails])

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.