We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Accounts Merge

Difficulty: Medium

Problem Description

Given a list of accounts where each element accounts[i] is a list of strings, where the first element accounts[i][0] is a name, and the rest of the elements are emails representing emails of the account. We would like to merge these accounts. Two accounts definitely belong to the same person if there is some common email to both accounts. After merging the accounts, return the accounts in the format: the first element of each account is the name, and the rest of the elements are emails in sorted order. The accounts themselves can be returned in any order.

Key Insights

  • Accounts with at least one common email should be merged.
  • The emails must be sorted in the final output.
  • The name associated with the emails is consistent for each person (but not necessarily unique across different people).
  • We can represent the problem as a graph where emails are nodes and edges exist between emails belonging to the same account.

Space and Time Complexity

Time Complexity: O(N * E log E), where N is the number of accounts and E is the number of emails, due to the sorting step. Space Complexity: O(N + E), for storing the email-to-name mapping and the merged accounts.

Solution

To solve the problem, we can use the Union-Find (Disjoint Set Union) data structure to group emails that belong to the same account. The steps are as follows:

  1. Create a mapping from each email to its corresponding account name.
  2. Use Union-Find to connect emails that belong to the same account.
  3. After processing all accounts, iterate through the connected components to group emails.
  4. For each group of emails, sort them and prepend the account name to form the final merged accounts list.

Code Solutions

class UnionFind:
    def __init__(self):
        self.parent = {}
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            self.parent[rootX] = rootY

def accountsMerge(accounts):
    uf = UnionFind()
    email_to_name = {}
    
    for account in accounts:
        name = account[0]
        first_email = account[1]
        if first_email not in uf.parent:
            uf.parent[first_email] = first_email
        email_to_name[first_email] = name
        
        for email in account[2:]:
            if email not in uf.parent:
                uf.parent[email] = email
            uf.union(first_email, email)
            email_to_name[email] = name
    
    email_groups = {}
    for email in uf.parent:
        root = uf.find(email)
        if root not in email_groups:
            email_groups[root] = []
        email_groups[root].append(email)
    
    merged_accounts = []
    for emails in email_groups.values():
        merged_accounts.append([email_to_name[emails[0]]] + sorted(emails))
    
    return merged_accounts
← Back to All Questions