721. Accounts Merge

721

MediumUnion-Find / Disjoint Set UnionUnion-Find over strings (emails)Merge by shared key

Accounts Merge

Each account is a list [name, email1, email2, ...]. Two accounts belong to the same person if they share at least one common email; a name may be reused by different people. Merge all accounts of the same person and return each merged account as its name followed by its emails sorted lexicographically. Accounts may be returned in any order.

Open official problem prompt ↗

In plain English

Cluster all emails that belong to the same real person and present each cluster as a name plus its sorted emails.

Picture it like this

Like consolidating duplicate contacts on a phone: if two entries share any phone number or email, they are the same person and get merged into one card.

Example

Input: accounts = [["John","johnsmith@mail.com","john_newyork@mail.com"],["John","johnsmith@mail.com","john00@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]
Output: [["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]
Why: The first two John accounts share johnsmith@mail.com so they merge; the third John shares no email so stays separate; Mary is untouched.

Constraints

1 <= accounts.length <= 10002 <= accounts[i].length <= 101 <= accounts[i][j].length <= 30accounts[i][0] consists of English lettersEmails consist of lowercase letters and exactly one '@'

Pattern lesson

See the pattern, then code

Merge by shared key

↗

Union-Find / Disjoint Set Union

Dynamic connectivity, merging groups, redundant edges, or Kruskal's algorithm.. Treat every email as a node and union all emails within the same account. Emails that end up under the same root belong to one person; attach the name (recorded per email) and sort each group.

New words, made simpleKnow these before the algorithm

Node = email: We union emails, not accounts, because emails are the shared identity keys.
Owner map: A side table from email to its name so we can label the final group.
Transitive merge: If A shares an email with B and B with C, then A, B, C all merge even without A and C sharing directly.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Graph + DFS

Correct, but building adjacency lists is more bookkeeping than needed.

Build a graph connecting emails in each account, then DFS each connected component.

Time O(N K log(N K))Space O(N K)

Best choiceUnion-Find over emails

Compact, and the final sort dominates the cost.

Union each account's emails to its first email, then bucket by root.

Time O(N K log(N K))Space O(N K)

The rule we keep true

Invariant

Two emails share a root if and only if they are transitively linked through a chain of accounts that share emails.

Why this is correct

Reasoning

Unioning every email in an account with a fixed anchor email of that account makes each account internally connected. Because shared emails appear in multiple accounts, their sets chain together, correctly capturing transitive identity. Bucketing by root then yields exactly the merged people.

The algorithm in three movesSay these aloud before coding

1Give each email its own set and record its owner name

union(johnsmith, john_newyork)

2For each account, union its first email with every other email in that account

union(johnsmith, john00) via 2nd account

3Bucket every email under its set root

root group: {johnsmith, john_newyork, john00}

4For each bucket, output the owner name followed by the sorted emails

output name John + sorted emails

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

john...smith0

john...ny1

john002

mary3

johnnybravo4

1 · ReadJohn: johnsmith, john_newyork

2 · AskNew emails?

3 · Update stateboth added, owner=John

4 · Resultunion(john_newyork, johnsmith)

Key takeaway

The shared johnsmith email links the first two accounts into one email set.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-4Maps
parent for the DSU forest, owner to remember each email's name.
2
Lines 12-18Register and union
Add unseen emails as their own root, stamp the name, and union every email to the account's first email.
3
Lines 20-22Bucket by root
Group all emails under their representative.
4
Lines 24Format output
Prepend the owner name and sort each group's emails lexicographically.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Two different people share the same name but no emails (must remain separate)
An account with a single email
The same email appearing in three or more accounts chaining several groups together

Common beginner mistakes

Unioning accounts by index instead of by email, which misses cross-account links
Forgetting to sort the emails in the final output
Using the name as a merge key, which wrongly fuses distinct people who share a name

Check your understanding

Why do we union emails rather than account indices?

PyPython 3 · solution.py

Optimal

1class Solution:2    def accountsMerge(self, accounts: list[list[str]]) -> list[list[str]]:3        parent: dict[str, str] = {}4        owner: dict[str, str] = {}56        def find(x: str) -> str:7            while parent[x] != x:8                parent[x] = parent[parent[x]]9                x = parent[x]10            return x1112        for acc in accounts:13            name, first = acc[0], acc[1]14            for email in acc[1:]:15                if email not in parent:16                    parent[email] = email17                owner[email] = name18                parent[find(email)] = find(first)1920        groups: dict[str, list[str]] = {}21        for email in parent:22            groups.setdefault(find(email), []).append(email)2324        return [[owner[root]] + sorted(emails) for root, emails in groups.items()]

Time complexityO(N K log(N K))Optimized

Space complexityO(N K)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

FacebookAmazonGoogle

Accounts Merge

Accounts Merge

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Union-Find / Disjoint Set Union