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.
Accounts Merge and Connected Components is a free DSA Interview Prep lesson on CoddyKit — lesson 4 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
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]})')Union Emails Within Each Account
For each account, we union the IDs of all emails listed together. We pick the first email in the account as the representative and union every other email's ID with it. This links all emails in the account into one component.
After processing all accounts, emails that appeared together (directly or transitively through shared emails across accounts) all share the same DSU root. This is the key step that propagates connectivity across multiple accounts.
class DSU:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
self.parent[self.find(x)] = self.find(y)
# After building email_to_id (from previous step)
# email_to_id = {'john@mail.com':0, 'john1@mail.com':1,
# 'john2@mail.com':2, 'mary@mail.com':3}
dsu = DSU(5) # 4 unique emails
# For account ['John', 'john@mail.com', 'john1@mail.com']:
dsu.union(0, 1) # john@ and john1@ share account => same component
# For account ['John', 'john1@mail.com', 'john2@mail.com']:
dsu.union(1, 2) # john1@ and john2@ share account => same component
# Now 0,1,2 all share a root; 3 (mary) is separate
print('find(0)==find(2)?', dsu.find(0) == dsu.find(2)) # True
print('find(0)==find(3)?', dsu.find(0) == dsu.find(3)) # FalseCollecting Emails per Component
After all unions are done, we iterate over every email, find its DSU root, and group emails by that root using a dictionary of lists. The root ID becomes the key. Finally, for each group, we retrieve the account name, sort the email list, and prepend the name.
Sorting the emails is required by the problem — within a merged account, emails must be in lexicographic order. The name can be retrieved from any email in the group (all emails in one component belong to the same person).
from collections import defaultdict
# After DSU unions, group by root
def collect_components(email_to_id, email_to_name, dsu):
root_to_emails = defaultdict(list)
for email, eid in email_to_id.items():
root = dsu.find(eid)
root_to_emails[root].append(email)
result = []
for root, emails in root_to_emails.items():
# Find the name from any email in this group
name = email_to_name[emails[0]]
result.append([name] + sorted(emails))
return result
# Mock data for illustration
email_to_id = {'john@m.com':0,'john1@m.com':1,'john2@m.com':2,'mary@m.com':3}
email_to_name = {e:'John' for e in list(email_to_id)[:3]}
email_to_name['mary@m.com'] = 'Mary'
class DSU:
def __init__(self,n): self.p=list(range(n))
def find(self,x): self.p[x]=self.p[self.p[x]] if self.p[x]!=x else x; return self.p[x] if self.p[x]==x else self.find(self.p[x])
def union(self,x,y): self.p[self.find(x)]=self.find(y)
dsu=DSU(4); dsu.union(0,1); dsu.union(1,2)
for row in collect_components(email_to_id, email_to_name, dsu):
print(row)Complete Accounts Merge Solution
Here is the complete solution combining all three steps: build the email-to-ID mapping, union emails within each account, and collect grouped emails by DSU root. The overall time complexity is O(n × m × alpha(n × m)) where n is the number of accounts and m is the maximum emails per account, which is effectively O(n × m).
Space complexity is O(n × m) for the email maps and DSU arrays. This solution handles the transitive merging correctly: if account A shares email X with account B, and account B shares email Y with account C, then A, B, and C are all merged into one group.
from collections import defaultdict
def accounts_merge(accounts):
email_to_id = {}
email_to_name = {}
eid = 0
for account in accounts:
name = account[0]
for email in account[1:]:
if email not in email_to_id:
email_to_id[email] = eid
eid += 1
email_to_name[email] = name
parent = list(range(eid))
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
parent[find(x)] = find(y)
for account in accounts:
first_id = email_to_id[account[1]]
for email in account[2:]:
union(first_id, email_to_id[email])
root_to_emails = defaultdict(list)
for email, i in email_to_id.items():
root_to_emails[find(i)].append(email)
return [[email_to_name[emails[0]]] + sorted(emails)
for emails in root_to_emails.values()]
accounts = [['John','a@m.com','b@m.com'],['John','c@m.com'],
['Mary','d@m.com'],['John','b@m.com','c@m.com']]
for row in accounts_merge(accounts):
print(row)BFS/DFS Alternative for Accounts Merge
An alternative approach builds an email-to-accounts graph where emails are nodes and edges connect emails that appear in the same account. Then BFS/DFS finds each connected component. While correct, this requires explicitly building the graph and running BFS from every unvisited email — more code and harder to reason about than DSU.
DSU is cleaner because the union-find structure naturally represents component membership without needing an explicit adjacency list. The only time BFS is preferable here is if you need to reconstruct the actual path or chain of shared emails between two accounts.
# BFS alternative (for comparison)
from collections import defaultdict, deque
def accounts_merge_bfs(accounts):
email_to_accounts = defaultdict(set)
for i, account in enumerate(accounts):
for email in account[1:]:
email_to_accounts[email].add(i)
visited_accounts = set()
result = []
for i, account in enumerate(accounts):
if i in visited_accounts:
continue
queue = deque([i])
emails_in_group = set()
while queue:
acc_idx = queue.popleft()
if acc_idx in visited_accounts:
continue
visited_accounts.add(acc_idx)
for email in accounts[acc_idx][1:]:
emails_in_group.add(email)
for j in email_to_accounts[email]:
queue.append(j)
result.append([account[0]] + sorted(emails_in_group))
return result
accounts = [['John','a@m.com','b@m.com'],['John','b@m.com','c@m.com'],['Mary','d@m.com']]
for row in accounts_merge_bfs(accounts):
print(row)Generalising: Graph Connected Components
The accounts-merge pattern generalises to any connected-components-with-labels problem: you have a set of items, some items are declared equivalent (connected), and you want to group all transitively equivalent items together. Examples include clustering problems, social-network friend groups, and duplicate record detection.
The general algorithm is always: (1) assign an integer ID to each item, (2) union IDs of declared-equivalent items, (3) group items by their DSU root. DSU is essentially a grouping engine for equivalence relations.
# Generalised grouping template
def group_equivalents(items, equivalences):
item_to_id = {item: i for i, item in enumerate(items)}
n = len(items)
parent = list(range(n))
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
parent[find(x)] = find(y)
for a, b in equivalences:
if a in item_to_id and b in item_to_id:
union(item_to_id[a], item_to_id[b])
groups = {}
for item in items:
root = find(item_to_id[item])
groups.setdefault(root, []).append(item)
return list(groups.values())
# Example: merging duplicate customer records
customers = ['Alice-NY','Alice-LA','Bob','Alice-TX','Carol']
links = [('Alice-NY','Alice-LA'),('Alice-LA','Alice-TX')]
print(group_equivalents(customers, links))Handling Edge Cases
Important edge cases in accounts merge:
- Single-email accounts: an account with only one email forms its own component unless another account shares that email.
- Same name, different people: 'John' appearing in two accounts does not mean they are the same person — only shared emails merge accounts. The name is stored per email, not per component.
- Empty accounts: an account with no emails should be skipped to avoid index errors.
Always verify your solution handles accounts that should not be merged just because they share a name. The DSU connections are driven solely by shared email addresses.
# Edge case: two Johns with no shared email => separate output
accounts = [
['John', 'john_a@m.com'],
['John', 'john_b@m.com'], # different email => different component
['Mary'], # no emails => skip
]
def accounts_merge_safe(accounts):
email_to_id = {}; email_to_name = {}; eid = 0
for account in accounts:
name = account[0]
for email in account[1:]:
if email not in email_to_id:
email_to_id[email] = eid; eid += 1
email_to_name[email] = name
parent = list(range(eid))
def find(x):
while parent[x]!=x: parent[x]=parent[parent[x]]; x=parent[x]
return x
def union(x,y): parent[find(x)]=find(y)
for account in accounts:
if len(account) < 2: continue # skip no-email accounts
first = email_to_id[account[1]]
for email in account[2:]:
union(first, email_to_id[email])
from collections import defaultdict
groups = defaultdict(list)
for email, i in email_to_id.items():
groups[find(i)].append(email)
return [[email_to_name[e[0]]] + sorted(e) for e in groups.values()]
for row in accounts_merge_safe(accounts):
print(row)Number of Connected Components in a Graph
A related problem (LeetCode 323) asks for the number of connected components in an undirected graph. This is simpler than accounts-merge: initialise DSU with n nodes, process all edges with union, then count distinct roots.
The most concise way to count components is to maintain a count variable starting at n and decrement it each time a successful union merges two different components. Alternatively, count the number of nodes i where find(i) == i at the end.
def count_components(n, edges):
parent = list(range(n))
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
count = n
for u, v in edges:
pu, pv = find(u), find(v)
if pu != pv:
parent[pu] = pv
count -= 1
return count
print(count_components(5, [[0,1],[1,2],[3,4]])) # 2: {0,1,2} and {3,4}
print(count_components(5, [[0,1],[1,2],[2,3],[3,4]])) # 1: all connected
print(count_components(5, [])) # 5: no edges, all isolatedSmallest Component and Largest Component
Once you have DSU with size tracking, you can answer queries like 'what is the size of the largest connected component?' or 'how many components have exactly 3 nodes?' in O(n) by scanning the size array at root nodes.
These queries appear in problems like 'find the largest connected island' on a grid or 'identify the smallest network partition'. After all unions are complete, scan for nodes i where find(i) == i (these are roots) and examine their sizes.
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py: return
if self.size[px] < self.size[py]: px, py = py, px
self.parent[py] = px
self.size[px] += self.size[py]
def component_stats(n, edges):
dsu = DSU(n)
for u, v in edges:
dsu.union(u, v)
sizes = [dsu.size[i] for i in range(n) if dsu.find(i) == i]
print('Component sizes:', sizes)
print('Largest component:', max(sizes))
print('Smallest component:', min(sizes))
print('Number of components:', len(sizes))
component_stats(8, [(0,1),(1,2),(3,4),(5,6),(6,7)])Interview Tips for DSU Problems
When you encounter a problem with merging groups, connectivity queries, or finding the extra edge, immediately think DSU. During interviews, mention both optimisations (path compression + union by rank/size) to demonstrate depth of knowledge, even if a simpler naive DSU would pass given the constraints.
Common mistakes to avoid: forgetting to handle the case where both endpoints are already connected (union is a no-op), using 0-indexed vs 1-indexed incorrectly, and not sorting the output for accounts-merge (the problem requires sorted email lists). Always clarify input constraints before coding.
# Interview checklist for DSU problems
checklist = [
'1. Identify: is this a grouping/connectivity/cycle problem?',
'2. Map problem entities to integer node IDs if needed',
'3. Implement DSU with path compression + union by rank/size',
'4. Process all relationships (edges/pairs) with union()',
'5. Answer queries using find() and size/count tracking',
'6. Handle edge cases: already connected, single nodes, no edges',
'7. Check output format: sorted? 1-indexed? Name included?',
'8. State time complexity: O(n * alpha(n)) ~ O(n)',
]
for item in checklist:
print(item)Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: accounts-merge is a connected-components problem where emails are nodes and accounts link emails, DSU solves it by mapping emails to integer IDs, unioning IDs within each account, and grouping by root, and the same DSU grouping template applies to any equivalence-class or clustering problem. Next up we switch gears to bit manipulation, starting with the fundamental AND, OR, XOR, NOT, and shift operators.
Frequently asked questions
Is the “Accounts Merge and Connected Components” lesson free?
Yes — the full text of “Accounts Merge and Connected Components” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “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. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 4 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Accounts Merge and Connected Components” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
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