Accounts Merge (LeetCode 721)

The problem

You get a list of accounts. Each account is a name followed by one or more emails. Two accounts belong to the same person if they share at least one email, and this is transitive: if A shares an email with B, and B with C, all three are one person. Merge them and return each person as [name, emails in sorted order]. Two different people can have the same name.

Input:
["John", "[email protected]", "[email protected]"]
["John", "[email protected]", "[email protected]"]
["Mary", "[email protected]"]

Output:
["John", "[email protected]", "[email protected]", "[email protected]"]
["Mary", "[email protected]"]

The two John accounts share [email protected], so they merge. Mary stays on her own.

How to think about it

Start with brute force. Compare every pair of accounts; if they share an email, merge them, and repeat until nothing changes. Each pass is O(A²·K) for A accounts of K emails, and you may need many passes because merges chain. Messy and slow.

The key insight: emails are nodes, and “same account” is an edge. Every email in one account belongs to the same person, so connect them. Two accounts that share an email are then automatically connected through it. The people are exactly the connected components of this email graph. Merging by name would be wrong, since names aren’t unique; the emails are what link accounts.

Union-find keeps it simple. You don’t need to build adjacency lists. For each account, union every one of its emails with the account’s first email (an anchor). That’s enough edges to connect the whole account. A shared email links two anchors together. At the end, find(email) gives each email’s group, so bucket emails by root, sort each bucket, and put the owner’s name in front.

Which pattern is this? Union-find over strings, using a dict for parent instead of a list. The tell is “group items that are linked, directly or through a chain of shared keys”.

Approach

1. Keep parent as a dict (find adds unseen keys as their own root) and owner mapping each email to a name.
2. For each account, for each email: record its owner, and union it with the account’s first email.
3. Group every email by find(email).
4. For each group, output [owner of root] + sorted(emails), and sort the final list.

Solution

from collections import defaultdict
def accounts_merge(accounts):
    parent = {}
    def find(x):
        parent.setdefault(x, x)                   # unseen email starts as its own root
        while parent[x] != x: parent[x] = parent[parent[x]]; x = parent[x]
        return x
    owner = {}
    for acc in accounts:
        name = acc[0]
        for email in acc[1:]:
            parent.setdefault(email, email); owner[email] = name
            parent[find(email)] = find(acc[1])    # union with this account's first email
    groups = defaultdict(list)
    for email in parent: groups[find(email)].append(email)
    return sorted([[owner[root]] + sorted(emails) for root, emails in groups.items()])
# accounts_merge([["John","[email protected]","[email protected]"],["John","[email protected]","[email protected]"],["Mary","[email protected]"]])
#   -> [["John","[email protected]","[email protected]","[email protected]"],["Mary","[email protected]"]]

Dry run

On the example:

Grouping by root gives [email protected]: [a, b, c] and [email protected]: [m]. The shared [email protected] is what pulled [email protected] into John’s first account.

Complexity

• Time: O(N log N) for N emails in total. The unions and finds are O(N·α(N)), nearly linear. Sorting the emails inside each group dominates.
• Space: O(N) for parent, owner and the groups.

Edge cases and pitfalls

• Same name, different people. Two “John” accounts with no shared email stay separate. Never union by name.
• Duplicate email inside one account is harmless: it’s unioned with its own group again.
• A later account linking two earlier ones. ["A","c@x","a@x"] after ["A","a@x","b@x"] and ["A","c@x"] merges all three. Union-find handles the chain without any extra passes.
• Forgetting to sort the emails in each group. The problem requires sorted order.
• Comparing parent[x] directly instead of find(x) when grouping. Always group by the true root.

Related problems

• Number of Connected Components (LeetCode 323): the same union-find, on integer nodes, counting groups.
• Redundant Connection (LeetCode 684): union-find used to detect the edge that closes a cycle.
• Group Anagrams (LeetCode 49): grouping by a shared key with a hash map, when links aren’t transitive.