⚡Flashcard Drill➔
NeetCode #584LC-721MediumGraphsNC 250
← Back to All Problems

#584 · #721 · Accounts Merge(账户合并)

📌 Problem Statement & Constraints

Given a list of accounts where accounts[i] = [name, email1, email2, ...], merge accounts that share any email. Two accounts belong to the same person if they share a common email. Return the merged accounts with emails sorted, in any order. Constraints: 1 <= accounts.length <= 1000, 1 <= emails per account <= 10.

💡 Core Algorithmic Approaches

  1. Union-find over emails: union every email in an account with the account's first email.
  2. Then group the emails by their root, and map each root to the account name.
  3. Sort each group's emails, and put the name first.
  4. The same person may appear under different account entries, which is exactly what the union step resolves.

💻 Benchmark Python3 Implementation

class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        from collections import defaultdict
        parent = {}

        def find(x: str) -> str:
            parent.setdefault(x, x)
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        def union(a: str, b: str) -> None:
            ra, rb = find(a), find(b)
            if ra != rb:
                parent[ra] = rb

        email_to_name = {}
        for acc in accounts:
            name = acc[0]
            for email in acc[1:]:
                email_to_name[email] = name
                union(acc[1], email)       # link every email to the account's first

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

        res = []
        for root, emails in groups.items():
            res.append([email_to_name[root]] + sorted(emails))
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(E * alpha(E) + E log E) where E is the total number of emails.
💾 Space Complexity
O(E) for the union-find and the grouping.

⚠️ Interview Pitfalls & Follow-ups

  • Unioning accounts instead of emails: emails are the shared keys.
  • Forgetting that one account may have several emails that need chaining: unioning each with the first handles it.
  • Not sorting the emails: the output requires sorted emails per account.
  • Using the account index as the union-find key: the accounts are not directly comparable; emails are.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems