Practice/Meta/Leetcode 721. Accounts Merge

Leetcode 721. Accounts Merge

CodingMust

Problem

You are given a collection of user accounts, where each account is represented as a list. The first element in each list is the account holder's name, and the remaining elements are email addresses associated with that account.

Your task is to merge accounts that belong to the same person. Two accounts definitely belong to the same person if they share at least one common email address. Note that even if two accounts have the same name, they may belong to different people if they don't share any email addresses.

After merging, each merged account should contain the person's name followed by all their email addresses in sorted order. The order of the accounts in the final result does not matter.

Requirements

1. Merge all accounts that share at least one email address
2. Each merged account must start with the person's name
3. All email addresses in each account must be sorted in lexicographic order
4. Remove duplicate email addresses within each merged account
5. The name alone does not determine if accounts belong to the same person - only shared emails do

Constraints

• 1 ≤ accounts.length ≤ 1000
• 2 ≤ accounts[i].length ≤ 10
• 1 ≤ accounts[i][j].length ≤ 30
• accounts[i][0] consists of English letters
• accounts[i][j] (for j > 0) is a valid email address
• Expected time complexity: O(N * K * log(K)) where N is the number of accounts and K is the maximum number of emails per account
• Expected space complexity: O(N * K)

Examples

Example 1:

` Input: [ ["Alice", "alice@mail.com", "alice@work.com"], ["Alice", "alice@work.com", "alice@personal.com"], ["Bob", "bob@mail.com"] ]

Output: [ ["Alice", "alice@mail.com", "alice@personal.com", "alice@work.com"], ["Bob", "bob@mail.com"] ]

Explanation: The first two accounts both contain "alice@work.com", indicating they belong to the same person. All three emails are combined and sorted. Bob's account is separate. `

Example 2:

` Input: [ ["John", "john1@mail.com"], ["John", "john2@mail.com"], ["John", "john3@mail.com"] ]

Output: [ ["John", "john1@mail.com"], ["John", "john2@mail.com"], ["John", "john3@mail.com"] ]

Explanation: These are three different people who happen to have the same name, since no emails overlap. `

Example 3:

` Input: [ ["Emma", "emma@a.com", "emma@b.com"], ["Emma", "emma@b.com", "emma@c.com"], ["Emma", "emma@c.com", "emma@d.com"] ]

Output: [ ["Emma", "emma@a.com", "emma@b.com", "emma@c.com", "emma@d.com"] ]

Explanation: Account 1 and 2 share emma@b.com, account 2 and 3 share emma@c.com, so all three accounts belong to the same person through transitive connections. `