iq.lab
Python starts when a code cell comes near or you run one
mediumUnion-findHash maps and setsSorting target 25 min

Merge the accounts

A sign-up system exports its accounts as a list accounts. Each account is a list of strings: the first is the owner's name, and the rest are the account's email addresses, at least one.

Two accounts belong to the same person when they share an email, and sharing chains: if account 0 shares an email with account 1, and account 1 shares a different email with account 2, all three are one person. Two people can have the same name, so a matching name proves nothing. All accounts of one person carry the same name. An email can appear in several accounts, and even twice in one account.

Return one list per person: the name, then every email of that person once, in sorted order (the order Python's sorted gives). The people can come in any order.

Example 1
Inputaccounts = [["Ana", "ana@work", "ana@home"], ["Ben", "ben@mail"], ["Ana", "ana@gym", "ana@home"], ["Ana", "ana@club", "ana@gym"]]Output[["Ana", "ana@club", "ana@gym", "ana@home", "ana@work"], ["Ben", "ben@mail"]]

Accounts 0 and 2 share ana@home, and accounts 2 and 3 share ana@gym. Accounts 0 and 3 share nothing directly, but account 2 links them, so all three are one Ana.

Example 2
Inputaccounts = [["Sam", "sam@uni"], ["Sam", "sam@shop"], ["Sam", "sam@art", "sam@uni"]]Output[["Sam", "sam@art", "sam@uni"], ["Sam", "sam@shop"]]

Accounts 0 and 2 share sam@uni. Account 1 shares no email with them, so it belongs to a different Sam.

Example 3
Inputaccounts = [["Lee", "lee@zoo", "lee@art", "lee@zoo"]]Output[["Lee", "lee@art", "lee@zoo"]]

One account is one person. Its emails come back sorted, and lee@zoo appears once.

Constraints
  • 1 ≤ len(accounts) ≤ 2 × 104

  • Each account is a name followed by 1 to 9 emails.

  • Names and emails are at most 30 characters long.

  • All accounts of one person have the same name.

Plan it first

Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.

⌘+Enter runs 0:00Python starts when a code cell comes near or you run one
Run examples checks the examples. Submit runs every test, including edge cases and, when the problem has one, a speed check on a large input.