MediumArrayHash TableStringDepth-First SearchBreadth-First SearchUnion FindSorting

Accounts Merge

1 approach, code in every language

You are given a list of accounts, where accounts[i] is [name, email1, email2, ...]. The first element is a person's name and the rest are the emails belonging to that account.

Two accounts definitely belong to the same person if they share at least one common email, even if the names look identical. Note that a single person can have any number of accounts, but all of their accounts use the same name; conversely, different people may share the same name.

Merge the accounts so that each person is represented once. Return the merged accounts in the format [name, sortedEmail1, sortedEmail2, ...], where the emails are sorted in lexicographic order. The accounts themselves may be returned in any order.

Example 1

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"]]

The first two John accounts share "johnsmith@mail.com", so they merge into one. The third John (johnnybravo) shares no email and stays separate, and Mary is untouched.

Example 2

Input: accounts = [["Alex","alex1@m.com","alex2@m.com"],["Alex","alex2@m.com","alex3@m.com"],["Bob","bob1@m.com"]]

Output: [["Alex","alex1@m.com","alex2@m.com","alex3@m.com"],["Bob","bob1@m.com"]]

The two Alex accounts share "alex2@m.com" and merge into one sorted list; Bob remains on his own.

Constraints

1 <= accounts.length <= 1000
2 <= accounts[i].length <= 10
1 <= accounts[i][j].length <= 30
accounts[i][0] consists of English letters.
accounts[i][j] (for j > 0) is a valid email address.

Union-Find on Emails

Union every email inside an account together, group emails by root, then sort each group and attach the owner name.

Loading animation…

Intuition

Two accounts belong to the same person when they share any email, and this shared-email relation is transitive, which is exactly what Union-Find models. Treat each distinct email as a node and union all emails that appear within the same account by linking every email to the account's first email. Alongside the disjoint set, keep a map from each email to the display name that owns it. Once all unions are done, every email that shares a person now shares a root, so collect emails by root into buckets, sort each bucket, and place the owner's name in front.

Algorithm walkthrough

1For each account, union its first email with each of the remaining emails so the whole account joins one set.
2Record the account name against every email so the owner can be recovered from any email later.
3After all unions, compute the root of every known email.
4Group emails into buckets keyed by their root.
5Sort each bucket lexicographically and prepend the name stored for that root's email.
6Collect the assembled rows and return them.

Implementation

class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        parent = {}
        owner = {}

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

        def union(a: str, b: str) -> None:
            parent[find(a)] = find(b)

        for account in accounts:
            name = account[0]
            first = account[1]
            for email in account[1:]:
                if email not in parent:
                    parent[email] = email
                owner[email] = name
                union(first, email)

        groups = {}
        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

Time

O(N * log N)

Space

O(N)

N is the total number of emails across all accounts. The union/find work is near-linear (amortized α per operation); the dominant cost is sorting the emails within each merged group.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Graphs

After the pattern

Now solve one you haven't seen.

Merge Crew Badge Records is our own problem on the technique behind Accounts Merge: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free