Two accounts belong to the same person if they share at least one email, and the relation is transitive: if account A shares an email with account B, and B shares an email with C, all three merge into one person even when A and C have no email in common.

A single round of pairwise comparisons cannot capture these chains. The structure that does is a graph: treat emails as nodes, let each account connect its emails, and every merged account is one connected component. Once the components are known, the rest is bookkeeping: collect each component's emails, sort them, and attach the name.

Key Constraints:

Intuition

If we think of each email as a node, and draw an edge between two emails whenever they appear in the same account, then finding merged accounts is the same as finding connected components in this graph.

Within a single account like ["John", "a@mail.com", "b@mail.com", "c@mail.com"], a, b, and c all belong together. Connecting every pair would add up to K^2 edges per account. Connecting each email to the first email in the account is enough: a-b, a-c. This star shape uses only K-1 edges, and connectivity is all that component detection needs, not direct edges between every pair.

Once the graph is built, we run DFS from each unvisited email, collecting all reachable emails into one group. Each group becomes one merged account. The DFS uses an explicit stack, so the traversal does not depend on recursion depth limits even when one component contains every email.

Algorithm

Example Walkthrough

Code

Union Find produces the same grouping without materializing an adjacency list or running a traversal.

Intuition

Union Find (also called Disjoint Set Union) maintains a partition of elements into disjoint groups and supports two operations: find the representative of an element's group, and union two groups into one. That matches this problem directly. Treat each email as an element and process accounts one at a time, unioning every email in an account with that account's first email.

After an account is processed, all of its emails share one root. When a later account contains an email that already belongs to some group, the union pulls that account's remaining emails into the same group. Root equality is transitive, so chains of shared emails across accounts merge without any explicit graph traversal. With path compression and union by rank, each operation costs nearly O(1). Union by rank also bounds every tree's height at O(log NK), so the recursive find stays shallow; path compression then flattens the chains it touches.

Algorithm

Example Walkthrough

Code

Approach 2 keys the Union Find on email strings, so the parent and rank maps hold one string entry per email and every operation hashes strings. The accounts themselves offer smaller identifiers: there are at most 1,000 of them, so integer indices from 0 to n-1 can serve as the Union Find elements, backed by two plain integer arrays.

Intuition

Treat each account, not each email, as a Union Find element. Maintain a map from email to the index of the first account that contained it. While scanning account i, each email falls into one of two cases: the email is new, so record i as its owner, or the email was already seen in account j, which proves accounts i and j belong to the same person, so union the two indices.

After the scan, every email's merged group is find(owner), the root of the account that first owned it. Grouping emails by that root and reading the name from accounts[root][0] produces the answer. The email map still holds one entry per email (building the output requires touching every email anyway), but the Union Find shrinks from string-keyed hash maps with an entry per email to two integer arrays with an entry per account.

Algorithm

Example Walkthrough

Code