Problem Statement
Accounts Merge
You get a list of accounts. Each account is a list of strings. The first string is a person's name, and the rest are email addresses for that account. The problem: one person can have several accounts. Two accounts belong to the same person if they share at least one email. We want to merge all accounts for the same person into one, with the name first and then the emails in sorted order. The accounts can be returned in any order. The main idea: think of each email as a clue that ties two accounts together. We use a tool called Union-Find to gather all the accounts that are connected through shared emails, then collect every email in each connected group.
Signals to notice
Brute force first
For each pair of accounts, check for shared emails. Quadratic comparison of all account pairs. That direct path helps you understand the question, but it tends to treat every possibility as brand new instead of learning from earlier steps.
The key insight
Union-Find on account indices. Map each email to the first account that owns it. When an email appears in a second account, union those two accounts. Then group emails by their root account. Once you hold onto the right piece of information from moment to moment, the problem feels less like trial and error and more like following a shape that was there all along.
Trace it on accounts=[["John","johnsmith@mail.com","john_newyork@mail.com"],["John","johnsmith@mail.com","john00@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]
init: parent=[0,1,2,3], email_to_id={}
i=0: map johnsmith->0, john_newyork->0
i=1: johnsmith seen at 0 -> union(1,0): parent[0]=1; map john00->1
i=2: map mary->2 | i=3: map johnnybravo->3
group by find(id): root1={johnsmith,john_newyork,john00}, root2={mary}, root3={johnnybravo}
emit: [John]+sorted(root1), [Mary]+sorted(root2), [John]+sorted(root3)
return [["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]What must stay true
Two accounts belong to the same person if they share any email. Union-Find transitively merges all accounts connected through shared emails into the same set. When you keep that truth intact, each local choice supports the larger solution instead of fighting it.
Shape of the loop
parent = identity over account indices
for i, account in accounts:
for email in account[1:]:
if email in email_to_id: union(i, email_to_id[email])
else: email_to_id[email] = i
for email, id in email_to_id: groups[find(id)].add(email)
return [[name(root)] + sorted(emails) for root, emails in groups]Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Unioning by email instead of by account — emails are the edges, accounts are the nodes. Map emails to account indices, then union the account indices. When the code becomes mechanical before the idea is clear, small edge cases start breaking the whole story.