All problems

Accounts Merge

Medium · union find

A website lets people sign up several times. You are given a list accounts. Each account is a list of strings: the first string is the name on the account, and the rest are the email addresses registered to it, for example ["Ava", "[email protected]", "[email protected]"].

Two accounts belong to the same person if they have at least one email address in common. This also works through other accounts: if account A shares an address with B, and B shares one with C, then A, B and C are all the same person, even if A and C share nothing directly.

Two accounts with the same name but no connection between them (directly or through others) are different people.

Merge the accounts. Return one entry per person: the name first, then every email address that person owns, each once.

The order is fixed:

• The people are listed in the order in which their first account appears in accounts.
• A person's emails are listed in the order you meet them when you read that person's accounts from the first to the last and each account from left to right. An address you have already listed is skipped.

Examples

Example 1

Input: accounts = [["Ava", "[email protected]", "[email protected]"], ["Ben", "[email protected]"], ["Ava", "[email protected]", "[email protected]"]]

Output: [["Ava", "[email protected]", "[email protected]", "[email protected]"], ["Ben", "[email protected]"]]

The two Ava accounts share [email protected], so they are one person. Their address [email protected] is listed once, and [email protected] comes last because it appears last. Ben is alone.

Example 2

Input: accounts = [["Sam", "[email protected]"], ["Sam", "[email protected]"]]

Output: [["Sam", "[email protected]"], ["Sam", "[email protected]"]]

Both accounts are called Sam, but they share no address, so they are two different people, listed in the order of their accounts.

Example 3

Input: accounts = [["Zoe", "[email protected]"], ["Kim", "[email protected]", "[email protected]"], ["Kim", "[email protected]", "[email protected]"], ["Kim", "[email protected]", "[email protected]"]]

Output: [["Zoe", "[email protected]"], ["Kim", "[email protected]", "[email protected]", "[email protected]", "[email protected]"]]

The third Kim account shares [email protected] with the first and [email protected] with the second, which joins all three into one person. Zoe's first account comes before Kim's, so she is listed first.

Constraints

• 1 <= len(accounts) <= 1000
• Each account has a name followed by between 1 and 10 email addresses, so 2 <= len(account) <= 11. An address may appear more than once in the same account.
• A name is 1 to 20 English letters (upper or lower case). An email address is 3 to 30 characters from lower-case letters, digits, '@' and '.'.
• If two accounts share an email address, they have the same name.