Accounts Merge
Merge account records that share common emails.
Pattern fit
Emails define connectivity across account rows, so the problem is really about grouping connected identifiers rather than traversing records one by one.
Key observation
The challenge is mapping string emails to DSU nodes and then grouping by final root.
Target complexity
O(n alpha(n)) / O(n)
How to break down the solution cleanly
Emails define connectivity across account rows, so the problem is really about grouping connected identifiers rather than traversing records one by one.
The challenge is mapping string emails to DSU nodes and then grouping by final root.
Initialize each node as its own parent.
Compress paths during find so future queries stay cheap.
Reference implementation
Python# Generic pattern template
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * 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, a, b):
pa, pb = self.find(a), self.find(b)
if pa == pb:
return False
if self.rank[pa] < self.rank[pb]:
pa, pb = pb, pa
self.parent[pb] = pa
if self.rank[pa] == self.rank[pb]:
self.rank[pa] += 1
return True
Common pitfalls
Unioning account indices but forgetting email-level mapping.
Collecting merged emails before path compression is complete.
Common follow-ups
Would graph traversal also work here?
What exactly should be the DSU node: account or email?
Continue with related problems
Build repeatable depth inside the Union Find cluster before moving on.