Accounts Merge and Connected Components
Group accounts sharing an email by treating emails as DSU nodes, then collect all emails per component to reconstruct merged accounts.
Problem: Accounts Merge
The Accounts Merge problem (LeetCode 721) gives a list of accounts, each being a list of strings where the first element is the account name and the rest are email addresses. Two accounts belong to the same person if they share at least one email. Merge all accounts belonging to the same person and return sorted email lists.
This is fundamentally a connected components problem where emails are nodes and a shared account links them. DSU is the ideal tool: union all emails within the same account, then collect emails per component.
# Example input
accounts = [
['John', 'john@mail.com', 'john1@mail.com'],
['John', 'john2@mail.com'],
['Mary', 'mary@mail.com'],
['John', 'john1@mail.com', 'john2@mail.com'],
]
# john@mail.com and john1@mail.com are in account[0]
# john1@mail.com and john2@mail.com are in account[3]
# => john@, john1@, john2@ are all the same person
# Expected output:
# ['John', 'john1@mail.com', 'john2@mail.com', 'john@mail.com']
# ['Mary', 'mary@mail.com']
print('Goal: merge accounts sharing any email into one account')Mapping Emails to Integer IDs
DSU works on integer indices, but our nodes are email strings. We need to map each unique email to an integer ID. We also need to remember which name owns each email. Use a dictionary email_to_id to assign incrementing IDs, and email_to_name to track the account name associated with each email.
Each unique email gets one ID. If the same email appears in multiple accounts, it maps to the same ID — and unioning the IDs of emails within one account connects them into a single component. The name associated with the root email's ID is the merged account name.
accounts = [
['John', 'john@mail.com', 'john1@mail.com'],
['John', 'john2@mail.com'],
['Mary', 'mary@mail.com'],
['John', 'john1@mail.com', 'john2@mail.com'],
]
email_to_id = {}
email_to_name = {}
next_id = [0]
for account in accounts:
name = account[0]
for email in account[1:]:
if email not in email_to_id:
email_to_id[email] = next_id[0]
next_id[0] += 1
email_to_name[email] = name
print('Total unique emails:', len(email_to_id))
for email, eid in email_to_id.items():
print(f' {email} => id {eid} (owner: {email_to_name[email]})')All lessons in this course
- DSU with Path Compression
- Union by Rank and the Inverse Ackermann Bound
- Redundant Connection and Cycle Detection
- Accounts Merge and Connected Components