Abstract / Summary

Given a list of accounts with names and emails, group accounts that share any email address and merge them into one account.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 62% (1+ million submissions).

Typical patterns to solve this problem:

• Array
• Breadth First Search
• Depth First Search
• Hash Table
• Sorting
• String
• Union Find

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the “accounts merge” problem by employing a union-find (disjoint set) data structure. Each account is initially treated as a separate component; email addresses that appear in multiple accounts trigger a union operation, collapsing the corresponding components. After all unions are performed, the algorithm gathers the emails belonging to each component, sorts them, and yields the merged account records.

Union-Find Initialization

parent = []                     # ID of each user, union-find to merge accounts
for i, a in enumerate(accounts):
    parent.append(i)            # each account starts as its own root

A list parent holds the representative (root) for each account index. The find function implements path compression, ensuring that subsequent look-ups reach the root directly.

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])   # path compression
    return parent[x]

Merging Accounts

Two auxiliary structures are built while iterating over the input:

• users stores the name associated with each original account (the first element of each sub-list).
• mails maps an email address to the root identifier of the account that first introduced it.

users = []                      # all names (duplicates allowed)
mails = {}                      # all address
for i, a in enumerate(accounts):
    users.append(a.pop(0))      # extract name, keep remaining emails
    for address in a:
        if address in mails:
            union(parent[i], mails[address])   # existing address, merge sets
        else:
            mails[address] = find(parent[i])   # first occurrence, record root

The union routine attaches the higher-indexed root to the lower-indexed one, preserving a deterministic ordering of roots.

def union(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if x < y:
        parent[y] = x
    else:
        parent[x] = y

Collecting Results

After all unions, a defaultdict(set) aggregates the email addresses belonging to each component. The second pass over accounts uses the final root of each account index to place emails into the appropriate bucket.

result = defaultdict(set)      # ID => merged addresses
for i, a in enumerate(accounts):
    for address in a:
        result[find(i)].add(address)

Finally, the algorithm yields each merged account. The name is taken from the users list using the component’s root index, and the email list is sorted to meet the required output format.

for r in result:               # convert to desired format
    yield [users[r]] + sorted(result[r])

Edge Cases Handled

The code gracefully handles accounts that contain a single email address, because the inner loop still processes that lone address and registers it in mails. When an email appears in multiple accounts, the union operation merges the corresponding components regardless of the order in which the accounts are read, thanks to the find calls that always retrieve the current root. Duplicate email entries within the same account are implicitly collapsed by the set used in result, preventing redundant entries in the final output. Accounts that share the same user name but have disjoint email sets remain separate components, as the union logic is driven solely by email overlap, not by name similarity.

Performance Optimizations

Path compression inside find dramatically reduces the depth of the union-find tree, making subsequent find operations near-constant time. The deterministic choice of the smaller index as the new root in union helps keep the tree shallow without requiring an explicit rank or size array. Storing the first occurrence of each email in the mails dictionary avoids repeated scans of previously seen addresses, turning the detection of overlapping emails into an O(1) hash-lookup per address. Using a defaultdict(set) for aggregation eliminates the need for explicit existence checks when inserting emails, and the final sorting step operates only on the distinct email set of each merged account, not on the entire input. These choices together ensure that the algorithm scales efficiently with the number of accounts and the total number of email addresses.

Imagine having lots of treasure chests filled with mail addresses that belong to different people. Some people have their mail scattered across several different chests, and the goal is to make sure all the addresses that belong to the same person end up in one single, organized chest.

The computer starts by giving every chest a special number tag so it can keep track of them. When it looks at the mail inside, it acts like a detective. If it finds the same address in two different places, it realizes those two chests must belong to the same person. It then uses a trick called union to link those chest numbers together so they act like one big group.

The finding part of the code works like following a string back to the very first anchor point. This ensures that every piece of mail knows exactly which group it belongs to, even if it was linked through many different chests.

Once the sorting is done, the computer gathers all the addresses linked to the same master group together. It puts them in a nice list, puts the person's name at the very front, and makes sure all the addresses are tucked away in alphabetical order. Now all the mail is perfectly organized, with no duplicates and everything exactly where it should be.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java	Python						TS
	WalkCCC	C++	Java
	leetcode.ca	C++	Java	Python					Go	TS
	LeetcodeHelp	C++	Java	Python
	Progiez	C++	Java	Python
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai		Java
	everthis				JS
	FelixFan1122		Java
	fpdjsns	C++
	gouthampradhan		Java
	halfrost								Go
	haoel	C++
	JoshCrozier				JS
	lkwq007			Python
	ruoru						Rust
	sonugiri1043	C++
	suxrobGM					C#
	trung-hn			Python
	varunu28		Java
	wisdompeak	C++
	yuanliu666							Kotlin
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
FelixFan1122	Java
fpdjsns	C++
gouthampradhan	Java
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
lkwq007	Python
ruoru	Rust
sonugiri1043	C++
suxrobGM	C#
trung-hn	Python
varunu28	Java
wisdompeak	C++
yuanliu666	Kotlin
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality