Accounts Merge
Picture
Accounts [a,b] and [b,c] share an email. A third record [c,d] joins indirectly, even without sharing a directly. The task needs a group of emails, not the path proving how those records connect.
Predict
Is a shared name enough to merge two records?
Walk through the small example
No. Two people can have the same name. Under this problem’s rules, shared email addresses establish identity; names merely label the output.
Mental model and complete Python solution
Give each account a DSU node. A dictionary stores the first account seen for each email. When an email repeats, union the current account with that first owner. Transitive unions naturally gather indirect matches. After all unions finish, group each distinct email by its owner’s final root, sort that group, and attach the account name. The representative is an implementation choice, not a meaningful person ID.
What the function promises: Each record contains a name followed by at least one email. Records linked to the same person use the same name, as guaranteed by the problem. Return merged records in any order, with sorted, unique emails within each record.
class DisjointSet:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
def find(self, x):
while x != self.parent[x]:
self.parent[x] = self.parent[self.parent[x]]
x = self.parent[x]
return x
def union(self, a, b):
a, b = self.find(a), self.find(b)
if a == b:
return False
if self.size[a] < self.size[b]:
a, b = b, a
self.parent[b] = a
self.size[a] += self.size[b]
return True
def merge_accounts(accounts):
groups = DisjointSet(len(accounts))
owner = {}
for i, account in enumerate(accounts):
for email in account[1:]:
if email in owner:
groups.union(i, owner[email])
else:
owner[email] = i
emails_by_root = {}
for email, i in owner.items():
root = groups.find(i)
emails_by_root.setdefault(root, []).append(email)
return [[accounts[root][0]] + sorted(emails)
for root, emails in emails_by_root.items()]
records = [["Ana", "a", "b"], ["Ana", "b", "c"],
["Ana", "c", "d"], ["Ana", "z"]]
assert sorted(merge_accounts(records)) == [
["Ana", "a", "b", "c", "d"], ["Ana", "z"]]
assert merge_accounts([]) == []Work and storage: For A accounts, E email occurrences, and U unique emails: O(A + E α(A) + U log U) expected time, plus string comparison costs when relevant; O(A+U) space. Union by size and path halving give the amortized DSU bound.
When to recognize it: Shared identity is transitive. We need groups, not the route connecting two records.
Check before applying it: Names can repeat across different people. Merge on shared emails under this problem’s contract, never on a matching name alone.
Change one rule
Instead, you need the shortest chain of shared-email links explaining a merge. Is the DSU parent chain that explanation?
See what changes
No. DSU parent pointers encode an optimized representative forest, not the original account connections. Keep the actual graph and use BFS if a shortest explanation path is required.
Connect
Union-find: Use find and union to represent shared membership.
Making A Large Island: After grouping, store a useful summary for each group.
Problem reference: Accounts Merge (Medium). The walkthrough and Python solution above are original course material.