Merge Accounts by Shared Email

Each account record begins with a person's name followed by one or more email addresses. Two records belong to the same person if they share at least one email address, directly or through a chain of shared addresses. Merge all records that refer to the same person.

Function Signature

def merge_accounts(accounts: list[list[str]]) -> list[list[str]]:
    ...

Input

• Each record has the form [name, email_1, email_2, ...].
• Every email address belongs to exactly one real person.
• Records for the same real person use the same name.

Output

Return one record per person. Each output record must contain the person's name followed by all of their distinct email addresses in lexicographic order. The order of person records does not matter.

Constraints

• 1 <= len(accounts) <= 10_000
• Each account contains at least one email address.
• The total number of email occurrences is at most 200_000.

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

One valid output:
[
  ["John", "john00@mail.com", "john_newyork@mail.com", "johnsmith@mail.com"],
  ["Mary", "mary@mail.com"],
  ["John", "johnnybravo@mail.com"]
]

Clarifications

• Sharing is transitive: if record A shares an email with B and B shares another email with C, all three records merge.
• Duplicate occurrences of the same email must appear only once in the merged record.

Merge Accounts by Shared Email

Merge account records connected directly or transitively by shared email, deduplicate and sort each person's emails. For deterministic grading, order merged person records by the earliest input-record index in each component.

Hints

1. Treat records sharing an email as connected components.
2. Union-find can merge components as each email is encountered.

Approach

The first owner of an email establishes a component; later occurrences union their records into it. A second pass collects unique emails by final root, emits each email set in lexicographic order, and orders components by their earliest input-record index.

• Time complexity: O(E alpha(A) + E log E) including email sorting
• Space complexity: O(A + E)