Accounts Merge

Table of Contents +

Accounts Merge feels like a real task from a real product. Think of a site like Amazon. One person may sign up many times with different emails. The site wants to know which accounts are really the same person. That is exactly this problem. And the clean tool for it is union-find.

🎯 The Problem

You get a list of accounts. Here are the rules.

Each account is a name followed by some emails.
Two accounts are the same person when they share at least one email.
The name alone proves nothing. Two different people can share a name.
For each merged group, output the name followed by all its emails.
The emails must be sorted with no repeats.

Look at an example. Account one is John with johnsmith@mail.com and john00@mail.com. Account two is John with johnsmith@mail.com and john_newyork@mail.com. Account three is Mary with mary@mail.com. Accounts one and two share johnsmith@mail.com, so they are the same John. Mary stands alone.

Input:
  ["John", "johnsmith@mail.com", "john00@mail.com"]
  ["John", "johnsmith@mail.com", "john_newyork@mail.com"]
  ["Mary", "mary@mail.com"]

Output:
  ["John", "john00@mail.com", "john_newyork@mail.com", "johnsmith@mail.com"]
  ["Mary", "mary@mail.com"]

Think of emails as nodes, which are points in a graph. Two emails are connected when they sit in the same account. A merged person is just one connected group of emails.

🐢 Approach 1: Compare All Account Pairs (Brute Force)

The idea in one line: check every pair of accounts for a shared email, merge, and repeat.

The idea:

Compare every account with every other account.
For each pair, check if they share any email.
If they do, merge them.

How it works:

After a merge, run another pass.
A merge can create new overlaps, so one pass is not enough.
Keep scanning until nothing changes.

Why it is weak:

Comparing all pairs is slow.
The repeat passes make it slower still.
When two accounts merge, a third might now connect to the bigger group. So you rescan again and again.

Here is the compare-all-pairs code:

def accounts_merge(accounts):
    parent = list(range(len(accounts)))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    def union(a, b):
        parent[find(b)] = find(a)
    for i in range(len(accounts)):
        emails_i = set(accounts[i][1:])
        for j in range(i + 1, len(accounts)):
            if emails_i & set(accounts[j][1:]):
                union(i, j)
    groups = {}
    for i, acc in enumerate(accounts):
        groups.setdefault(find(i), set()).update(acc[1:])
    return [[accounts[i][0]] + sorted(emails) for i, emails in groups.items()]

🚀 Approach 2: Union-Find on Emails (Best)

The idea in one line: treat each email as an item, union emails inside an account, and shared emails merge people for free.

The idea:

Union-find, also called disjoint set union, groups items into sets.
It answers “are these two in the same set?” almost instantly.
Find tells you which set an item belongs to. Union joins two sets into one.

How it works:

Treat every email as an item.
Inside one account, union the first email with each of the other emails.
That ties all emails of one account together.
If an email already appeared in an earlier account, the union links the two accounts through it.
Keep a small map from each email to its owner’s name. The name only labels the output.
After all unions, every connected group has one root, the single representative of the set.
Sweep all emails, bucket them by root, sort each bucket, attach the name.

Why it is fast:

Each find and union is almost constant time.
Path compression flattens the tree during find, so later lookups jump straight to the root.
Union by size attaches the smaller tree under the bigger one, keeping trees short.

Here is how the parent pointers look after we process John’s two accounts. Every John email points to the same root.

Steps to Solve

Give each unique email a slot in the union-find structure.
Map each email to the name of the account it first appeared in.
For each account, union the first email with every other email in it.
After all unions, find the root of every email.
Group emails by their root into buckets.
Sort the emails in each bucket.
Output the name plus the sorted emails for each bucket.

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

This Python version keeps a parent dictionary keyed by email, so the union-find works straight on the email strings.

def accounts_merge(accounts):
    parent = {}        # email -> its parent email
    owner = {}         # email -> the account name

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]   # path compression
            x = parent[x]
        return x

    def union(a, b):
        parent[find(a)] = find(b)

    for acc in accounts:
        name = acc[0]
        first = acc[1]
        for email in acc[1:]:
            if email not in parent:
                parent[email] = email       # new email is its own root
            owner[email] = name
            union(first, email)             # tie all emails of this account

    groups = {}        # root email -> list of emails
    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


accounts = [
    ["John", "johnsmith@mail.com", "john00@mail.com"],
    ["John", "johnsmith@mail.com", "john_newyork@mail.com"],
    ["Mary", "mary@mail.com"],
]
for group in sorted(accounts_merge(accounts)):
    print(", ".join(group))

The output of the above code will be:

John, john00@mail.com, john_newyork@mail.com, johnsmith@mail.com
Mary, mary@mail.com

Let us read the Python version line by line. Code first, then the why.

We keep two dictionaries. parent maps each email to its parent email. owner maps each email to the account name. The name is only for the label at the end.

find(x) climbs from an email to the root of its set. The line parent[x] = parent[parent[x]] is path compression. It points the email at its grandparent on the way up, which flattens the tree. So later finds are faster. union(a, b) joins two sets by pointing one root at the other.

Now the merge loop. For each account we take first = acc[1], the first email. Then for email in acc[1:] walks every email including the first. If the email is new we set parent[email] = email, making it its own root. We record owner[email] = name. Then union(first, email) ties every email of this account to the first one. If that first email already lived in an earlier account, this union silently links the two accounts. That is how a shared email merges two people with no special code.

After the loop we group by root. for email in parent walks every email. root = find(email) gets its representative. groups.setdefault(root, []).append(email) drops the email into the bucket for its root. Each bucket is one person.

Finally we build the answer. For each bucket, [owner[root]] + sorted(emails) puts the name first, then the emails in sorted order. Sorting is required by the problem. The outer sorted(...) in the print loop just makes the output order steady for the example.

⏱️ Time and Space Complexity

Let n be the total number of emails across all accounts. Union-find with path compression makes each find and union almost constant. So the merging is close to O(n). The slow part is the final sort inside each group, which costs O(n log n) overall. The space holds the parent map, the owner map, and the groups, so it is O(n).

Approach	Time Complexity	Space Complexity
Compare all account pairs (brute force)	O(n² * passes)	O(n)
Union-find on emails	O(n log n) from the sort	O(n)

Tip

The insight to say out loud is this. The name never decides anything. Only a shared email merges accounts. Once you see emails as nodes and shared emails as edges, union-find is the obvious fit.

🧩 Key Takeaways

✅ Two accounts are the same person only when they share an email, never by name alone.
✅ Treat each email as a node. A shared email connects two accounts.
✅ Union all emails inside one account, so a repeated email links accounts automatically.
✅ After all unions, group emails by their root, sort each group, and attach the name.
✅ Path compression keeps union-find almost constant time per operation.

Check Your Knowledge

4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

🚀 What’s Next?

Word Ladder
Shortest Path in Binary Matrix

Previous Word Ladder II Next Shortest Path in Binary Matrix

Accounts Merge

Follow Us

Follow Us