What is the brute force approach and complexity for Accounts Merge?

Repeatedly merge any two groups that share an email, rescanning after each merge with time complexity O(N³ · K log M) and space complexity O(N · K).

What is the optimal approach and complexity for Accounts Merge?

Give each email an id, union within each account, group emails by root, then sort with optimal time complexity O(N · K · α + M log M) and space complexity O(M).

How do you identify the pattern for Accounts Merge?

Look for key signals in the prompt: "accounts that share an email belong to the same person" indicates A shared email joins two groups. Chains of shared emails join more.; "same name, but may be different people" indicates The name is not the key. The email is what links accounts.; "emails in sorted order, name first" indicates An output step after the groups are final, not part of the grouping..

Accounts Merge

Medium·LeetCode #721 Pro OnlyBasic Reinforcement

LeetCode

Problem Statement

You get a list of accounts. Each account is a list of strings: the first string is the owner's name, and the rest are the emails on that account.

Two accounts belong to the same person when they share at least one email. The rule chains: if A shares an email with B, and B shares one with C, then A, B and C are all one person. Two accounts with the same name can still be different people.

Merge the accounts that belong to one person. Each merged account is the name, followed by all of that person's emails in sorted order. Return the merged accounts in any order.

Input

accounts: a list of accounts. Each account is [name, email1, email2, ...].

Output

A list of merged accounts. Each one is [name, sorted emails...]. The order of the accounts in the answer does not matter.

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 Johns share johnsmith@mail.com, so they are one person. The third John shares no email with anyone, so he stays separate, even though the name is the same.

Example 2

Input: accounts = [["Ann", "a@m.co", "b@m.co"], ["Ann", "c@m.co", "b@m.co"]]

Output: [["Ann", "a@m.co", "b@m.co", "c@m.co"]]

The two accounts share b@m.co, so they merge into one account with three sorted emails.

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

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“accounts that share an email belong to the same person”

→ A shared email joins two groups. Chains of shared emails join more.

“same name, but may be different people”

→ The name is not the key. The email is what links accounts.

“emails in sorted order, name first”

→ An output step after the groups are final, not part of the grouping.

Approach Complexity Ladder

Brute Force — merge accounts until nothing changesO(N³ · K log M)O(N · K)

Repeatedly merge any two groups that share an email, rescanning after each merge

Optimal — union the emails of each account, then group by rootO(N · K · α + M log M)O(M)

Give each email an id, union within each account, group emails by root, then sort

Brute Force Intuition

Start with one group per account. Find any two groups that share an email, merge them, and rescan from the start. When a full scan finds no pair to merge, the groups are final: sort each group's emails and put the name first.

Recognition rule for this sub-pattern:

"a equals b", "same owner", "can swap" — union them, then process each group together.

Remember this · Union-Find (DSU)

Trigger

Edges arrive one by one, "are these connected?", merge equivalent items, count components, extra edge creating a cycle.

Think

Am I repeatedly merging groups and asking whether two things are in the same group?

Key question

What are the elements, and what does it mean to union two of them?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Union-Find (DSU) translate into production architectures and low-level memory mechanics.

LLD Architecture