DSA Accounts Merge

The problem

Accounts Merge gives a list of account records. Each record holds one name and one or more email addresses.

Two records belong to the same person when they share any email address. The answer merges each person's records into one record. Emails inside a record print sorted, and records print ordered by their first email.

cases = [
    ([["Ana", "ana@x.com", "ana@y.com"],
      ["Ana", "ana@y.com", "ana@z.com"],
      ["Ben", "ben@x.com", "ben@y.com"],
      ["Ana", "ana@w.com"],
      ["Ben", "ben@y.com", "ben@z.com"]],
     [["Ana", "ana@w.com"],
      ["Ana", "ana@x.com", "ana@y.com", "ana@z.com"],
      ["Ben", "ben@x.com", "ben@y.com", "ben@z.com"]]),
    ([["Ana", "a@x.com", "b@x.com"],
      ["Ana", "b@x.com", "c@x.com"],
      ["Ana", "c@x.com", "d@x.com"]],
     [["Ana", "a@x.com", "b@x.com", "c@x.com", "d@x.com"]]),
    ([["Ana", "a@x.com"], ["Ben", "b@x.com"]],
     [["Ana", "a@x.com"], ["Ben", "b@x.com"]]),
]
for accounts, expected in cases:
    print("accounts:", len(accounts), "-> merged:", len(expected))
    for acc in expected:
        print(acc)

Ana holds three records in the first case, and only two of them share an email. The third stays separate. Sharing decides the merge, never the name alone.

Intuition: group by the first email

The first idea files each record under its first email. Records with the same first email land together. The filing looks complete after one pass.

accounts = [["Ana", "a@x.com", "b@x.com"], ["Ana", "b@x.com", "c@x.com"]]
groups = {}
for acc in accounts:
    groups.setdefault(acc[1], []).append(acc)
print("groups by first email:", len(groups))
print("shared email: b@x.com appears in both records")
print("true merged accounts: 1")

The two records share b@x.com, but their first emails differ. The filing keeps them apart and reports two accounts for one person. Any shared email must merge, not just a shared first email.

Brute force: merge any two records that share an email, then repeat

The brute force compares record pairs. Two records that share an email merge into one. A merge can create new sharings, so the passes repeat until a full pass merges nothing.

def merge_brute(accounts):
    groups = []
    for acc in accounts:
        groups.append([acc[0], set(acc[1:])])
    comparisons = 0
    changed = True
    while changed:
        changed = False
        for i in range(len(groups)):
            if changed:
                break
            for j in range(i + 1, len(groups)):
                comparisons += 1
                if groups[i][1] & groups[j][1]:
                    groups[i][1] |= groups[j][1]
                    del groups[j]
                    changed = True
                    break
    merged = [[name] + sorted(emails) for name, emails in groups]
    merged.sort(key=lambda acc: acc[1])
    return merged, comparisons

accounts = [
    ["Ana", "ana@x.com", "ana@y.com"],
    ["Ana", "ana@y.com", "ana@z.com"],
    ["Ben", "ben@x.com", "ben@y.com"],
    ["Ana", "ana@w.com"],
    ["Ben", "ben@y.com", "ben@z.com"],
]
merged, comparisons = merge_brute(accounts)
for acc in merged:
    print(acc)
print("comparisons:", comparisons)

Five records settle into three accounts. The comparison counter shows the price. Every merge restarts the pairing, and later passes recheck pairs that never change.

The optimal solution: union the emails of each record

Union-find groups the email addresses themselves, and unioning each record's first email with its other emails puts one root over every address of one person. That one sentence is the whole method.

A root is the name of a set. Records whose emails share a root merge into one account. The owner's name comes from any record that holds the root email.

def merge_accounts(accounts):
    parent = {}

    def find(x):
        parent.setdefault(x, x)
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(a, b):
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[rb] = ra

    owner = {}
    unions = 0
    for acc in accounts:
        name = acc[0]
        for email in acc[1:]:
            owner[email] = name
            find(email)
        for email in acc[2:]:
            union(acc[1], email)
            unions += 1
    groups = {}
    for email in sorted(owner):
        groups.setdefault(find(email), []).append(email)
    merged = []
    for root in groups:
        emails = sorted(groups[root])
        merged.append([owner[root]] + emails)
    merged.sort(key=lambda acc: acc[1])
    return merged, unions

cases = [
    ([["Ana", "ana@x.com", "ana@y.com"],
      ["Ana", "ana@y.com", "ana@z.com"],
      ["Ben", "ben@x.com", "ben@y.com"],
      ["Ana", "ana@w.com"],
      ["Ben", "ben@y.com", "ben@z.com"]],
     [["Ana", "ana@w.com"],
      ["Ana", "ana@x.com", "ana@y.com", "ana@z.com"],
      ["Ben", "ben@x.com", "ben@y.com", "ben@z.com"]]),
    ([["Ana", "a@x.com", "b@x.com"],
      ["Ana", "b@x.com", "c@x.com"],
      ["Ana", "c@x.com", "d@x.com"]],
     [["Ana", "a@x.com", "b@x.com", "c@x.com", "d@x.com"]]),
    ([["Ana", "a@x.com"], ["Ben", "b@x.com"]],
     [["Ana", "a@x.com"], ["Ben", "b@x.com"]]),
]
for accounts, expected in cases:
    merged, unions = merge_accounts(accounts)
    print("merged:", len(merged), "union calls:", unions, "match:", merged == expected)

All three cases pass. Four union calls settle the first case, against nine comparisons for the brute force.

Walkthrough: five records, one at a time

The groups below grow record by record. Each line prints every group after one more record is processed. Groups print as sorted email lists, ordered by their first email.

accounts = [
    ["Ana", "ana@x.com", "ana@y.com"],
    ["Ana", "ana@y.com", "ana@z.com"],
    ["Ben", "ben@x.com", "ben@y.com"],
    ["Ana", "ana@w.com"],
    ["Ben", "ben@y.com", "ben@z.com"],
]
parent = {}

def find(x):
    parent.setdefault(x, x)
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(a, b):
    ra, rb = find(a), find(b)
    if ra != rb:
        parent[rb] = ra

for i, acc in enumerate(accounts):
    for email in acc[1:]:
        find(email)
    for email in acc[2:]:
        union(acc[1], email)
    groups = {}
    for acc2 in accounts[:i + 1]:
        for email in acc2[1:]:
            groups.setdefault(find(email), set()).add(email)
    print("after record", i + 1, ":", sorted(sorted(g) for g in groups.values()))

Record four adds a group instead of joining one. Its email appears nowhere else, so Ana gains a second account. The final three groups are the three merged accounts.

Complexity

The brute force compares record pairs again after every merge, so its comparisons grow faster than the record count. Union-find makes one union call per extra email, so its work grows with the total email count.

Both methods store one entry per email, so their extra space is O(emails).

def merge_brute(accounts):
    groups = []
    for acc in accounts:
        groups.append([acc[0], set(acc[1:])])
    comparisons = 0
    changed = True
    while changed:
        changed = False
        for i in range(len(groups)):
            if changed:
                break
            for j in range(i + 1, len(groups)):
                comparisons += 1
                if groups[i][1] & groups[j][1]:
                    groups[i][1] |= groups[j][1]
                    del groups[j]
                    changed = True
                    break
    return comparisons

def union_calls(accounts):
    parent = {}

    def find(x):
        parent.setdefault(x, x)
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    calls = 0
    for acc in accounts:
        for email in acc[1:]:
            find(email)
        for email in acc[2:]:
            ra, rb = find(acc[1]), find(email)
            if ra != rb:
                parent[rb] = ra
            calls += 1
    return calls

def make(m):
    accounts = []
    for i in range(m):
        accounts.append(["A", "a" + str(i) + "@x.com", "a" + str(i + 1) + "@x.com"])
        accounts.append(["B", "b" + str(i) + "@x.com", "b" + str(i + 1) + "@x.com"])
    return accounts

for m in (2, 3, 4):
    accounts = make(m)
    print("accounts", len(accounts), "- brute comparisons:", merge_brute(accounts), " union calls:", union_calls(accounts))

At eight accounts the brute force pays 22 comparisons against 8 union calls. Each restart rechecks settled pairs. Union-find never revisits a settled record.

Edge cases and pitfalls

An empty list merges to an empty list. A record with one email forms an account on its own.

The same email twice in one record is a duplicate, not a second address. The merged record lists it once.

def merge_accounts(accounts):
    parent = {}

    def find(x):
        parent.setdefault(x, x)
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(a, b):
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[rb] = ra

    owner = {}
    unions = 0
    for acc in accounts:
        name = acc[0]
        for email in acc[1:]:
            owner[email] = name
            find(email)
        for email in acc[2:]:
            union(acc[1], email)
            unions += 1
    groups = {}
    for email in sorted(owner):
        groups.setdefault(find(email), []).append(email)
    merged = []
    for root in groups:
        emails = sorted(groups[root])
        merged.append([owner[root]] + emails)
    merged.sort(key=lambda acc: acc[1])
    return merged, unions

print("no accounts:", merge_accounts([])[0])
print("one small account:", merge_accounts([["Ana", "a@x.com"]])[0])
print("duplicate email:", merge_accounts([["Ana", "a@x.com", "a@x.com"]])[0])
print("same name, no sharing:", merge_accounts([["Ana", "a@x.com"], ["Ana", "b@x.com"]])[0])

The last case is the name trap. Two records share the name Ana and no email. They stay apart, because the name is a label and the email is the evidence.