Accounts Merge

Each account row starts with a name followed by one or more email addresses: [name, email1, email2, ...].

Two rows belong to the same person if they share any email address, directly or through a chain of overlaps. Merge all connected rows.

For this judge, keep the output deterministic:

• sort the emails within each merged account in ascending lexicographic order;
• sort the final merged accounts by (name, firstEmail) ascending.

Input / output

• Input: accounts: string[][]
• Output: string[][] where each row is [name, sortedEmail1, sortedEmail2, ...]

Examples

1. accounts = [["John","johnsmith@mail.com","john_newyork@mail.com"],["John","johnsmith@mail.com","john00@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]] returns [["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],["John","johnnybravo@mail.com"],["Mary","mary@mail.com"]]. The first two John rows merge because they share johnsmith@mail.com.
2. accounts = [["Alex","a@mail.com"],["Alex","b@mail.com"],["Alex","a@mail.com","c@mail.com"]] returns [["Alex","a@mail.com","c@mail.com"],["Alex","b@mail.com"]]. Only the rows connected through a@mail.com merge.
3. accounts = [["Eve","eve@mail.com","eve2@mail.com"],["Eve","eve2@mail.com","eve3@mail.com"]] returns [["Eve","eve2@mail.com","eve3@mail.com","eve@mail.com"]]. Email overlap can connect more than two rows.

Constraints

• 1 <= accounts.length <= 1000
• 2 <= accounts[i].length <= 10
• Account names contain letters.
• Email strings are non-empty and case-sensitive.

Edge cases

• Multiple people may share the same name but not any email.
• A merged component can span many rows.
• Single-row accounts should still be returned.

Target complexity

• Aim for near-linear union-find work over all email occurrences, plus sorting the final email lists.

Hints

1. Treat each input row as a node and union two rows when they mention the same email.
2. After unioning, gather every email under its component root, sort those emails, then build the deterministic output rows.

Follow-up How would you solve the same problem with a graph traversal over emails instead of union-find?