Loading page…
Practice problem · easy
You work on an online shop. Some customers made several accounts over the years. Each account lists the email addresses it was used with. To keep the data small, each email address is stored as an id number.
Two accounts belong to the same customer when they share an email address. The link can also go through other accounts. If account 0 shares an email with account 1, and account 1 shares one with account 2, then all three are one customer. Your team lead says: "Mark every account with the lowest account number of its customer, so we can merge them."
Write merge_accounts(accounts).
accounts[i] is the list of email ids on account i. The accounts are numbered 0 to len(accounts) - 1.result with one entry for each account. result[i] is the lowest account number among all the accounts of the same customer as account i.An account with no email ids is its own customer. An account can list the same email id twice.
Input: accounts = [[5, 7], [9], [7, 3], [9, 2], [4]]
Output: [0, 1, 0, 1, 4]Go through the accounts in order. For each email id, remember the first account that had it. When a later account has the same id, the two accounts are one customer.
| Account | Email ids | What happens | Customers so far |
|---|---|---|---|
| 0 | 5, 7 | both are new: owned by account 0 | {0} |
| 1 | 9 | new: owned by account 1 | {0} {1} |
| 2 | 7, 3 | 7 is owned by account 0, so 2 joins 0. 3 is new | {0, 2} {1} |
| 3 | 9, 2 | 9 is owned by account 1, so 3 joins 1. 2 is new | {0, 2} {1, 3} |
| 4 | 4 | new | {0, 2} {1, 3} {4} |
The lowest account number is 0 for accounts 0 and 2, 1 for accounts 1 and 3, and 4 for account 4. The answer is [0, 1, 0, 1, 4].
Input: accounts = [[1], [2], [1, 2]]
Output: [0, 0, 0]Accounts 0 and 1 share no email. Account 2 has both emails, so it links them: all three are one customer.
Input: accounts = [[], [], [8]]
Output: [0, 1, 2]Accounts 0 and 1 have no email ids, so each is its own customer. Account 2 is alone too.
1 ≤ len(accounts) ≤ 100,0000 to 100 email ids, and all the accounts together list at most 200,0000 to 10,000,000There can be 100,000 accounts. Comparing every pair of accounts costs n² pairs: 10 billion comparisons, each one a look through two lists. Instead, remember the first account that listed each email id, and join each later account to it. Every email id is then looked at once.
merge_accounts · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.