Introduction

Accounts Merge is a popular Union Find (DSU) problem.

You are given:

  • Multiple accounts
  • Each account contains a name and emails
  • Two accounts belong to the same person if they share at least one email

Goal

Merge all accounts belonging to the same person.

Example

Input

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

Key Observation

Two accounts should be merged if they share at least one common email.

Therefore:

Emails act as connections between accounts.
If two accounts share an email,they belong to the same connected component.Union Find efficiently groups such accounts.

Algorithm

  1. Initialize DSU for all accounts.
  2. Map each email to its account index.
  3. If an email already exists, union both accounts.
  4. Group emails using ultimate parent.
  5. Sort emails inside each component.
  6. Build final answer.

Dry Run

Input

0 → John → a@mail b@mail1 → John → b@mail c@mail
2 → Mary → d@mail

Processing

b@mail appears in account 0 and account 1Union(0,1)

Parent:
0 → 0
1 → 0
2 → 2

Components

Parent 0:a@mail
b@mail
c@mail

Parent 2:
d@mail

Answer

[["John","a@mail","b@mail","c@mail"],
["Mary","d@mail"]
]

Approach : Union Find (DSU)

Accounts sharing emails belong to the same connected component, so Union Find is used to merge them efficiently.

Practice

Time Complexity: O(N × M × α(N) + E log E)Explanation:
Each email is processed once for Union Find operations.The final emails inside every component are sorted before generating the answer.

Space Complexity: O(N + E)
Explanation:
Extra space is used for the parent array, email mapping,and grouped email storage.

Why This Problem is Important

Accounts Merge teaches how Union Find can be used for grouping and connectivity problems involving real-world data.

Common Beginner Mistakes

  • Using names instead of emails for merging.
  • Forgetting path compression.
  • Not sorting emails in the final answer.
  • Grouping using account index instead of parent.

Interview Tip

Always mention that emails form connections between accounts and Union Find groups all connected accounts efficiently.

Related Questions

  • Redundant Connection
  • Graph Valid Tree
  • Number of Provinces
  • Number of Connected Components in an Undirected Graph
  • Making A Large Island

Final Takeaway

Accounts Merge is a classic DSU problem where emails act as edges connecting accounts.

Mastering it helps in solving advanced connectivity and grouping problems using Union Find.