Problem 50 · Graphs

Accounts Merge

MediumClassic DSA & systems

01Problem

Given accounts as [name, email1, email2, ...], merge accounts that share any email and return each merged account as name followed by its sorted emails.

02Key insight

Emails are nodes; each account unions its emails together. Group emails by DSU root. This is entity resolution, the same pattern used for identity stitching in data platforms.

03Solution

solution.pypython21 lines

from collections import defaultdict

def accounts_merge(accounts: list[list[str]]) -> list[list[str]]:
    parent: dict[str, str] = {}

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

    owner: dict[str, str] = {}
    for name, *emails in accounts:
        for email in emails:
            owner[email] = name
            parent[find(email)] = find(emails[0])
    groups: dict[str, list[str]] = defaultdict(list)
    for email in owner:
        groups[find(email)].append(email)
    return [[owner[root]] + sorted(emails) for root, emails in groups.items()]

Try it first.

TimeO(N*a(N) + N log N)

SpaceO(N)

tests.py · 3 passing

tests.pypython4 lines

res = accounts_merge([["John","a@x","b@x"],["John","c@x"],["John","b@x","d@x"],["Mary","m@x"]])
assert sorted(res) == [["John","a@x","b@x","d@x"],["John","c@x"],["Mary","m@x"]]
assert accounts_merge([]) == []
assert accounts_merge([["A","e@x","e@x"]]) == [["A","e@x"]]

04Staff-level follow-up

Billions of records in Databricks/Snowflake? Run distributed connected components (iterative label propagation or large-star/small-star) over the email-account bipartite graph.