Accounts Merge

Intuition

Two accounts belong to the same person when they share any email, and this shared-email relation is transitive, which is exactly what Union-Find models. Treat each distinct email as a node and union all emails that appear within the same account by linking every email to the account's first email. Alongside the disjoint set, keep a map from each email to the display name that owns it. Once all unions are done, every email that shares a person now shares a root, so collect emails by root into buckets, sort each bucket, and place the owner's name in front.

Algorithm walkthrough

1. 1For each account, union its first email with each of the remaining emails so the whole account joins one set.
2. 2Record the account name against every email so the owner can be recovered from any email later.
3. 3After all unions, compute the root of every known email.
4. 4Group emails into buckets keyed by their root.
5. 5Sort each bucket lexicographically and prepend the name stored for that root's email.
6. 6Collect the assembled rows and return them.

Implementation

class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        parent = {}
        owner = {}

        def find(x: str) -> str:
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        def union(a: str, b: str) -> None:
            parent[find(a)] = find(b)

        for account in accounts:
            name = account[0]
            first = account[1]
            for email in account[1:]:
                if email not in parent:
                    parent[email] = email
                owner[email] = name
                union(first, email)

        groups = {}
        for email in parent:
            root = find(email)
            groups.setdefault(root, []).append(email)

        result = []
        for root, emails in groups.items():
            result.append([owner[root]] + sorted(emails))
        return result