Merge Accounts That Share an Email
You are given a list accounts. Each account is a list of strings: the first string is a name, and the rest are emails that belong to that account.
Two accounts belong to the same person if they have at least one email in common. This joins in chains: if account A shares an email with B, and B shares an email with C, then A, B and C all belong to one person, even if A and C share nothing.
Two accounts with the same name but no shared email (directly or through a chain) belong to different people. Accounts of one person always have the same name.
Merge the accounts of each person into one account: [name, email1, email2, ...], where each email appears once.
Return the merged accounts in this exact form:
- Inside each account, the emails are sorted in increasing order.
- The accounts are sorted by their first email in increasing order.
Note
- Strings are compared character by character using character codes (the normal string comparison in JavaScript and Python).
- No email belongs to two different people, so every first email is different and the order is always clear.
Hint: treat every email as a node, and join all emails of one account together. Union-find or a graph search then gives the groups.
Examples
Example 1
- Input:
- [["Ravi","ravi@web.in","r.k@mail.com"],["Meera","meera@web.in"],["Ravi","ravi.k@job.in","r.k@mail.com"]]
- Output:
- [["Meera","meera@web.in"],["Ravi","r.k@mail.com","ravi.k@job.in","ravi@web.in"]]
The two Ravi accounts both have r.k@mail.com, so they are one person. Their three emails are sorted. Meera comes first because meera@web.in is smaller than r.k@mail.com.
Example 2
- Input:
- [["Sam","sam1@x.org"],["Sam","sam2@x.org"]]
- Output:
- [["Sam","sam1@x.org"],["Sam","sam2@x.org"]]
The two accounts have the same name but no email in common, so they are two different people.
Example 3
- Input:
- [["Lea","b@q.net","c@q.net"],["Lea","a@q.net","b@q.net"],["Lea","c@q.net","d@q.net"]]
- Output:
- [["Lea","a@q.net","b@q.net","c@q.net","d@q.net"]]
The first account shares b@q.net with the second and c@q.net with the third, so all three join into one account.
Constraints
1 <= accounts.length <= 82 <= accounts[i].length <= 5(a name plus 1 to 4 emails)- Names are made of letters. Emails use only lowercase letters, digits,
@and.. - The emails inside one account are all different.
Run checks your code against the 3 examples. Submit checks it against all 103 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.