Accounts Merge - Leetcode Solution

The Accounts Merge problem on LeetCode is a problem in which we have to merge two or more accounts with the same owner. Each account includes a list of emails, which means that if two or more accounts have the same email, then they should be merged. We have to return a list of accounts that have been merged.

Let's start with understanding the problem statement.

Problem Statement: Given a list of accounts where each account has a name and a list of emails, merge the accounts with the same email.

Input:

The input to this problem is a list of accounts. Each account is represented as a list of strings, where the first element is the name of the account, and the remaining elements are the emails associated with the account.

Output:

The output of this problem should be a list of merged accounts. Each merged account should have the same name as the corresponding account in the input list and should include all the emails that were associated with the corresponding accounts in the input list.

Algorithm:

We can solve this problem by using the Union-Find algorithm. We will create a disjoint-set of all the emails, where each email is represented as a node in the disjoint-set. We will also create a hashmap to map each email to an account. Initially, each email node will belong to its own set.

We will then iterate through each account and add a relationship between the email nodes in the account. For each account, we will loop over its email nodes. For each email node, we will merge it with the first email node in the account.

After all the account nodes have been merged, we will create a new hashmap and populate it with the representative email node and the list of emails associated with it. Finally, we will iterate through this hashmap and add the merged accounts to the answer list.

Pseudocode:

class EmailNode:
    def __init__(self, email, account):
        self.email = email
        self.account = account
        self.parent = self

class Solution:
    def accountsMerge(self, accounts):
        
        # create disjoint-set for email nodes
        email_nodes = {email: EmailNode(email, account) for account in range(len(accounts)) for email in accounts[account][1:]}
        
        # merge email nodes in each account
        for account in range(len(accounts)):
            for i in range(1, len(accounts[account])-1):
                self.union(email_nodes[accounts[account][i]], email_nodes[accounts[account][i+1]])
        
        # create hashmap with representative email nodes
        merged_accounts = {}
        for email in email_nodes:
            parent = self.find(email_nodes[email])
            if parent not in merged_accounts:
                merged_accounts[parent] = [accounts[parent.account][0], []]
            merged_accounts[parent][1].append(email)
        
        # create list of merged accounts
        ans = []
        for account in merged_accounts.values():
            account[1].sort()
            ans.append([account[0]] + account[1])
        
        return ans
    
    def union(self, node1, node2):
        root1 = self.find(node1)
        root2 = self.find(node2)
        if root1 != root2:
            root2.parent = root1
    
    def find(self, node):
        if node.parent == node:
            return node
        node.parent = self.find(node.parent)
        return node.parent

Time Complexity:

The time complexity of the above algorithm is O(n log n), where n is the total number of emails in all accounts. This is because we execute a union-find operation on each of the emails, which requires log n time. We also iterate over each account and each email in the account, which takes O(n) time. Therefore, the overall time complexity is O(n log n).

Space Complexity:

The space complexity of the above algorithm is O(n), where n is the total number of emails in all accounts. This is because we need to store all the email nodes in the disjoint-set and the hashmap.

1