721. Accounts Merge - Detailed Explanation

Problem Statement

You are given a list of accounts where each account is represented as a list of strings. The first string is a name, and the remaining strings are email addresses. Two accounts definitely belong to the same person if there is any common email between them. Even if two accounts have the same name, they may not belong to the same person unless they share an email.

Your Task:
Merge the accounts so that each account contains all the unique emails of a single person, then return the merged account in the following format:

• The first element is the name.

• The rest of the elements are the unique email addresses in sorted lexicographical order.

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

Explanation:
The first two accounts belong to the same person (John) because they share the email "johnsmith@mail.com". They are merged into one account with all unique emails sorted in lexicographic order. The other two accounts do not share any common emails with any other accounts, so they remain separate.

Hints

• Graph/Union-Find Idea:
  Think of each email as a node in a graph. Two emails are connected if they appear in the same account. The problem then reduces to finding all connected components (subgraphs) in the graph. A common way to solve this is to use Union-Find (also known as Disjoint Set Union, DSU).

• Mapping Emails to Names:
  While grouping emails, it is essential to remember which name they belong to. For every email you process, store a mapping from the email to the corresponding account name.

• Merging Process:
  Once you have grouped all emails using union-find (or DFS), sort each group of emails, prepend the name, and that forms one merged account.

Approach Explanation (Using Union-Find)

Step 1: Initialize Data Structures

• Union-Find Structure:
  Create a union-find data structure to efficiently join connected emails.

• Email-to-Name Mapping:
  For every email encountered, map it to the name from the account.

Step 2: Process Each Account

• For each account, iterate through its emails:
  • For every pair of emails in the same account, use the union operation to join them.
  • This ensures that all emails in the same account are connected in the union-find structure.

Step 3: Group Emails by Root Parent

• After processing all accounts, iterate through every email.
• Use the union-find "find" operation to determine the root parent of each email.
• Group emails by their root parent in a dictionary.

Step 4: Construct the Final Output

• For each group (each unique root), sort the list of emails lexicographically.
• Retrieve the name (using the mapping) and form the merged account as a list (with the name as the first element).

Python Code Implementation