Coding Interview PatternsAccounts Merge
MediumUnion Find

Accounts Merge

Explanation & Solution

Practice Problem

Description

Given a list of accounts where each element accounts[i] is a list of strings, where the first element accounts[i][0] is a name, and the rest of the elements are emails representing emails of the account.

Now, we would like to merge these accounts. Two accounts definitely belong to the same person if there is some common email to both accounts. After merging, return the accounts in the following format: the first element of each account is the name, and the rest are emails sorted in order. The accounts themselves can be returned in any order.

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

Explanation: The first and second John accounts share "johnsmith@mail.com", so they are merged. The third John has no common email with the others.

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] (j > 0) is a valid email

Approach

Union Find pattern

1. Initialize Union Find with Email Keys

  • Use a Map-based Union Find where each email is a node
  • Track parent and rank for path compression and union by rank
  • Also maintain an emailToName map to remember which name owns each email

2. Union Emails Within Each Account

  • For each account, union all emails together using the first email as the anchor
  • This connects all emails in the same account into one component
  • If two accounts share an email, their entire email sets get merged transitively

3. Group Emails by Root

  • Iterate over all emails and find their root representative
  • Group emails into a Map keyed by their root
  • Each group represents one merged account

4. Build Result

  • For each component, sort the emails alphabetically
  • Prepend the account name (looked up from emailToName)
  • Add to the result array

Key Insight

  • Union Find naturally handles transitive merging: if account A shares an email with B, and B shares with C, all three merge
  • Using emails as Union Find keys avoids index mapping complexity
Time
**O(n · α(n))** for union-find operations plus **O(n log n)** for sorting emails, where n is total emails
Space
O(n) for the Union Find structures and grouping maps

Solution Code

Previous
Longest Consecutive Sequence
Next
Satisfiability of Equality Equations