204. Accounts Merge

Why this mechanism works

Emails are identity evidence and account indices are convenient DSU elements. Remember the first account that owns each email; every later occurrence unions its account with that owner. After all unions, group each distinct email by its owner's final representative.

State and boundaries

owner maps each email to an account containing it. DSU components represent all shared-email links processed so far.

Protocol

1. Create one DSU element per account.
2. Union accounts sharing an email.
3. Find the final root for every distinct email's owner.
4. Group emails by root.
5. Prefix the consistent name, sort emails, and sort records.

Visualization

[Ana,a,b] + [Ana,b,c] -> [Ana,a,b,c]
[Ana,z] stays separate: same name is not shared-email evidence

Python implementation

from collections import defaultdict
from kata_201 import DSU

def merge_accounts(accounts):
    dsu, owner = DSU(len(accounts)), {}
    for i, account in enumerate(accounts):
        for email in account[1:]:
            if email in owner:
                dsu.union(i, owner[email])
            else:
                owner[email] = i
    groups = defaultdict(list)
    for email, i in owner.items():
        groups[dsu.find(i)].append(email)
    return sorted([accounts[root][0]] + sorted(emails)
                  for root, emails in groups.items())

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L5 merge_accounts: dsu, owner = DSU(len(accounts)), {}
accounts=[['Ana', 'a', 'b'], ['Ana', 'b', 'c'], ['Ana', 'z']]; dsu=DSU{'parent':[..., ..., ...], 'size':[..., ..., ...], 'count':3}; owner={}

L6 merge_accounts: for i, account in enumerate(accounts):
accounts=[['Ana', 'a', 'b'], ['Ana', 'b', 'c'], ['Ana', 'z']]; dsu=DSU{'parent':[..., ..., ...], 'size':[..., ..., ...], 'count':3}; owner={}; i=0; account=['Ana', 'a', 'b']

L7 merge_accounts: for email in account[1:]:
accounts=[['Ana', 'a', 'b'], ['Ana', 'b', 'c'], ['Ana', 'z']]; dsu=DSU{'parent':[..., ..., ...], 'size':[..., ..., ...], 'count':3}; owner={}; i=0; account=['Ana', 'a', 'b']; email='a'

L11 merge_accounts: owner[email] = i
accounts=[['Ana', 'a', 'b'], ['Ana', 'b', 'c'], ['Ana', 'z']]; dsu=DSU{'parent':[..., ..., ...], 'size':[..., ..., ...], 'count':3}; owner={'a':0}; i=0; account=['Ana', 'a', 'b']; email='a'

L7 merge_accounts: for email in account[1:]:
accounts=[['Ana', 'a', 'b'], ['Ana', 'b', 'c'], ['Ana', 'z']]; dsu=DSU{'parent':[..., ..., ...], 'size':[..., ..., ...], 'count':3}; owner={'a':0}; i=0; account=['Ana', 'a', 'b']; email='b'

L11 merge_accounts: owner[email] = i
accounts=[['Ana', 'a', 'b'], ['Ana', 'b', 'c'], ['Ana', 'z']]; dsu=DSU{'parent':[..., ..., ...], 'size':[..., ..., ...], 'count':3}; owner={'a':0, 'b':0}; i=0; account=['Ana', 'a', 'b']; email='b'

L6 merge_accounts: for i, account in enumerate(accounts):
accounts=[['Ana', 'a', 'b'], ['Ana', 'b', 'c'], ['Ana', 'z']]; dsu=DSU{'parent':[..., ..., ...], 'size':[..., ..., ...], 'count':3}; owner={'a':0, 'b':0}; i=1; account=['Ana', 'b', 'c']; email='b'

L9 merge_accounts: dsu.union(i, owner[email])
accounts=[['Ana', 'a', 'b'], ['Ana', 'b', 'c'], ['Ana', 'z']]; dsu=DSU{'parent':[..., ..., ...], 'size':[..., ..., ...], 'count':2}; owner={'a':0, 'b':0}; i=1; account=['Ana', 'b', 'c']; email='b'

... 14 intermediate state changes omitted ...

L15 <genexpr>: return sorted([accounts[root][0]] + sorted(emails)
.0=dict_itemiterator; accounts=[['Ana', 'a', 'b'], ['Ana', 'b', 'c'], ['Ana', 'z']]

L16 <genexpr>: for root, emails in groups.items())
.0=dict_itemiterator; accounts=[['Ana', 'a', 'b'], ['Ana', 'b', 'c'], ['Ana', 'z']]; root=1; emails=['a', 'b', 'c']

L16 <genexpr>: for root, emails in groups.items())
.0=dict_itemiterator; accounts=[['Ana', 'a', 'b'], ['Ana', 'b', 'c'], ['Ana', 'z']]; root=2; emails=['z']

L16 <genexpr>: for root, emails in groups.items())
.0=dict_itemiterator; accounts=[['Ana', 'a', 'b'], ['Ana', 'b', 'c'], ['Ana', 'z']]; root=2; emails=['z']

L5 merge_accounts: dsu, owner = DSU(len(accounts)), {}
accounts=[]; dsu=DSU{'parent':[], 'size':[], 'count':0}; owner={}

L12 merge_accounts: groups = defaultdict(list)
accounts=[]; dsu=DSU{'parent':[], 'size':[], 'count':0}; owner={}; groups={}

L15 <genexpr>: return sorted([accounts[root][0]] + sorted(emails)
.0=dict_itemiterator; accounts=[]

Why the solution is correct

Every union is justified by a shared email, and every shared-email occurrence creates the necessary union. DSU transitivity therefore matches exactly the identity relation. Grouping distinct email keys by final roots includes every email once in its correct merged account.

Time and space

O(A+T*alpha(A)+T log T) coarse time for A accounts and T email occurrences, including output sorting; O(A+T) auxiliary/output storage. String comparison costs depend on lengths.

Common mistakes

Merging by name combines unrelated people. Grouping before all unions are complete can split accounts whose connection appears later.

Reasoning card

Transfer exercise

Remove the consistent-name guarantee and define how conflicting names should be surfaced instead of silently choosing one.