Strategy:
Map each email to an account index
If an email appears in multiple accounts, union those accounts
Collect all emails for each root account
def accountsMerge(accounts):
uf = UnionFind(len(accounts))
emailToId = {}
# Map emails to account indices
for i, account in enumerate(accounts):
for email in account[1:]:
if email in emailToId:
uf.union(i, emailToId[email])
emailToId[email] = i
# Collect emails by root
rootToEmails = defaultdict(set)
for email, id in emailToId.items():
root = uf.find(id)
rootToEmails[root].add(email)
# Build result
result = []
for root, emails in rootToEmails.items():
name = accounts[root][0]
result.append([name] + sorted(emails))
return result