LeetCode #721 Medium

Accounts Merge

Merge accounts that share at least one email into a single account per person, since the same person may have multiple listed accounts.

graphunion-findhash-table

Open on LeetCode ↗

02

Intuition

💡

The trap is merging on the person's NAME. Two different people can easily share a name, so name is never a safe key for identity -- the real identity is the EMAIL. Union every pair of emails that co-occur inside one account, since owning the same account proves they belong to the same person. After all unions, group every email by its Union-Find root: each group is one real person's full email set. The name is only a label attached at the very end, read off any account that happened to own one of the emails in that group -- it plays no role in the merging logic itself.

03

Approach

1

Union emails within each account

For each account, treat its first email as the anchor and union every other email in that account with it. This links all emails an account claims, regardless of the account's name.

2

Group by root, not by name

After processing every account, find() every email to get its root, and bucket all emails sharing a root together -- that bucket is exactly one person's merged emails, even if it came from several differently-named accounts.

3

Attach a name only for output

Pick the name from any account that owned one email in the group (they must agree it's the same person's data) and prepend it to the sorted email list -- purely cosmetic, never used for merging.

04

Solution & live demo

python

▶1class Solution:
▶2    def accountsMerge(self, accounts):
▶3        parent = {}
▶4        owner = {}
▶5        def find(x):
▶6            parent.setdefault(x, x)
▶7            while parent[x] != x:
▶8                parent[x] = parent[parent[x]]
▶9                x = parent[x]
▶10            return x
▶11        def union(a, b):
▶12            ra, rb = find(a), find(b)
▶13            if ra != rb:
▶14                parent[ra] = rb
▶15        for acc in accounts:
▶16            name, emails = acc[0], acc[1:]
▶17            for e in emails:
▶18                owner[e] = name       # identity is the EMAIL
▶19                union(emails[0], e)
▶20        groups = {}
▶21        for e in owner:
▶22            groups.setdefault(find(e), []).append(e)
▶23        result = []
▶24        for root, emails in groups.items():
▶25            result.append([owner[emails[0]]] + sorted(emails))
▶26        return result

05

Edge cases

Two different people happen to share a name

Their emails never got unioned (no shared email), so they remain separate groups despite the same name.

One person has 3+ accounts all sharing one email

All emails end up under one root via chained unions through the common email.

Account with only one email, no overlaps

Stays its own singleton group.

Emails must be returned sorted within each group

Sort each group's email list before prepending the name, per the problem's required output format.

06

Complexity

Time

O(N log N)

Space

O(N)

N = total emails across all accounts; dominated by sorting each merged group.