LeetCode Solutions Blog

Accounts Merge

Number: 721

Difficulty: Medium

Paid? No

Problem Description

Given a list of accounts where each account contains a name and emails, merge accounts that share any common emails. After merging, each account should list the name followed by the emails in sorted order.

Key Insights

Two accounts are merged if they share at least one common email.
Treat each email as a node in a graph; accounts represent connected components.
Both DFS/BFS and Union-Find can be used to find connected components.
Keep a mapping from email to name because all emails in a connected component belong to the same person.
After grouping, sort the emails and prepend the name to form the final account list.

Space and Time Complexity

Time Complexity: O(N * M * log(M)) where N is the number of accounts and M is the number of emails per account (owing to sorting and union operations).
Space Complexity: O(N * M), used for storing email mappings and union-find structures.

Solution

The solution involves using a Union-Find (Disjoint Set Union) data structure to merge emails that are connected by being on the same account. For each account, we union the first email with every other email in that account. We also maintain a mapping from email to owner name. After processing all accounts, we group the emails by their root parent derived from the union-find structure. For each group, we sort the emails and prepend the owner's name. Finally, we return the merged list of accounts.

Code Solutions

# Python solution for Accounts Merge

# Define the UnionFind class for disjoint set operations
class UnionFind:
    def __init__(self):
        self.parent = {}
    
    # Find with path compression
    def find(self, x):
        if self.parent.setdefault(x, x) != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    # Union two nodes
    def union(self, x, y):
        self.parent[self.find(x)] = self.find(y)

class Solution:
    def accountsMerge(self, accounts):
        uf = UnionFind()
        email_to_name = {}
        
        # Iterate over each account and union emails
        for account in accounts:
            name = account[0]
            first_email = account[1]
            for email in account[1:]:
                uf.union(first_email, email)
                email_to_name[email] = name
        
        # Group emails by their root parent
        groups = {}
        for email in email_to_name:
            parent = uf.find(email)
            groups.setdefault(parent, []).append(email)
        
        # Return the merged account list with sorted emails
        result = []
        for parent, emails in groups.items():
            result.append([email_to_name[parent]] + sorted(emails))
        return result

# Example usage:
# accounts = [["John","johnsmith@mail.com","john_newyork@mail.com"],
#             ["John","johnsmith@mail.com","john00@mail.com"],
#             ["Mary","mary@mail.com"],
#             ["John","johnnybravo@mail.com"]]
# solution = Solution()
# print(solution.accountsMerge(accounts))