The O(n) Club: Accounts Merge: When Emails Collide, but Names Are Lying

The O(n) Club: Accounts Merge — When Emails Collide, but Names Are Lying

⚡ TL;DR

If two user accounts share an email, guess what? They’re the same person rocking a multi-alias life. Merge their emails and move on. No, names are not unique: “Ash Ketchum” has more accounts than Pikachu has evolutions. Brute force? Sure, if you like slow-motion train wrecks:

// Brute force (spoiler: don't do this)
for (int i = 0; i < accounts.size(); i++) {
  for (int j = i + 1; j < accounts.size(); j++) {
    if (anySharedEmail(accounts.get(i), accounts.get(j))) {
      // Brutal merge (prepare for lag)
    }
  }
}

🧠 How Devs Usually Mess This Up

Picture this: Someone merges by name, then wonders why “John Smith” is receiving emails for “John Smith, Jr.” and “Jon Smit.” Mistake #1: assuming names are unique. Mistake #2: forgetting that emails must be sorted, so the test harness keels over and your interviewer bites their notebook in half. Cycling through accounts for cycle detection? Also unnecessary—both DSU and DFS handle overlap effortlessly. Seriously, only merge if an email overlaps. The rules here are stricter than airport security.

🔍 What’s Actually Going On

Imagine each account as a club membership sheet, and each email is a universal access pass. If two sheets list the same pass, they’re part of one big, happy club. The algorithm’s real job? Find all people secretly connected by any common email, even if their names look like someone mashed the keyboard. In Java, this is a graph thing: emails as nodes, accounts as cliques, merge connected cliques. Disjoint Set Union (DSU) is your backstage pass for performance; DFS works too, but DSU is what the cool devs use.

🛠️ PseudoCode

• Prepare email mappings:
  • For each email in each account, map it to the account’s index.

  // Map<String, Integer> emailToIndex

• Unify accounts using DSU:
  • If two accounts share the same email, merge (union) them. Now they’re inseparable—algorithmically speaking.

  // parent[] array for DSU

• Group emails by their top ancestor:
  • Find the DSU root for each email. Build sets of emails that share the same ancestor.

  // Map<Integer, Set<String>> indexToEmails

• Format output with sorted emails:
  • Attach the owner’s name and a TreeSet of emails (TreeSet means auto-sorted—free snacks!).

  // [Name, email1, email2, ...]

💻 The Code

// Java - Union-Find (Disjoint Set Union)
class Solution {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        Map<String, Integer> emailToIndex = new HashMap<>();
        Map<String, String> emailToName = new HashMap<>();
        int n = accounts.size();
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        // Link emails and accounts
        for (int i = 0; i < n; i++) {
            String name = accounts.get(i).get(0);
            for (int j = 1; j < accounts.get(i).size(); j++) {
                String email = accounts.get(i).get(j);
                emailToName.put(email, name);
                if (!emailToIndex.containsKey(email)) {
                    emailToIndex.put(email, i);
                } else {
                    union(parent, i, emailToIndex.get(email));
                }
            }
        }
        Map<Integer, Set<String>> indexToEmails = new HashMap<>();
        for (String email : emailToIndex.keySet()) {
            int root = find(parent, emailToIndex.get(email));
            indexToEmails.computeIfAbsent(root, x -> new TreeSet<>()).add(email);
        }
        List<List<String>> res = new ArrayList<>();
        for (int idx : indexToEmails.keySet()) {
            List<String> merged = new ArrayList<>();
            merged.add(accounts.get(idx).get(0));
            merged.addAll(indexToEmails.get(idx));
            res.add(merged);
        }
        return res;
    }
    private int find(int[] parent, int x) {
        if (parent[x] != x) parent[x] = find(parent, parent[x]);
        return parent[x];
    }
    private void union(int[] parent, int a, int b) {
        parent[find(parent, a)] = find(parent, b);
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Assuming names are gospel: They’re not unique, they’re not reliable, and they’re definitely not for merging.
• Sorting emails isn’t a suggestion: It’s a requirement. Use TreeSet if you like breathing easy.
• Duplicate emails? Set them straight. Literally, use a Set.
• Complexity check: Union-Find brings you close to O(Nα(N)). Translation: really fast unless you run your app on a potato.

🧠 Interviewer Brain-Tattoo

Merging by name? You’re asking for a headache in 3…2…1. “When in doubt, let the emails sort things out.” — O(n) Club