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
- Union-find over emails: union every email in an account with the account's first email.
- Then group the emails by their root, and map each root to the account name.
- Sort each group's emails, and put the name first.
- 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.