Accounts Merge

Problem

You are given a list of account records. Each record is a list of strings whose first entry is a person's display name and whose remaining entries are email addresses that belong to that account.

Two records belong to the same person if they share at least one email address, and this relation is transitive: if A shares an email with B and B shares one with C, then A, B, and C are all the same person. Two people can have the same display name; that alone does not merge them.

Merge the records and return one list per person, formatted as the name followed by that person's distinct emails in sorted (ASCII) order. The order of the people in the output does not matter.

• Up to a few thousand records; each holds a name plus between one and a dozen emails.
• Names and emails are short ASCII strings (a few dozen characters at most).
• Every record has at least one email, and all records that end up merged carry the same name.

Examples

• [["Priya","[email protected]","[email protected]"],["Priya","[email protected]","[email protected]"],["Tom","[email protected]"],["Priya","[email protected]"]] → [["Priya","[email protected]","[email protected]","[email protected]"],["Priya","[email protected]"],["Tom","[email protected]"]]. The first two Priya records share [email protected]; the third Priya shares nothing and stays a separate person.
• [["Lee","[email protected]","[email protected]"],["Lee","[email protected]"],["Lee","[email protected]","[email protected]"]] → [["Lee","[email protected]","[email protected]","[email protected]"]]. The last record bridges the first two, so all three collapse into one person.
• [["Sam","[email protected]"],["Sam","[email protected]"],["Sam","[email protected]"]] → three unchanged records. Same name, no shared email, no merge.

Hints

1. Think of each email as a node. What connects two nodes?
2. The answer is one group per connected component. Which structure finds components incrementally as you read records?
3. Union-find keyed by email (or by account index); then group emails by their root and sort each group.