Accounts Merge Leetcode Problem 721 [Python Solution]

In this blog post, we'll dive into the Accounts Merge problem from LeetCode, categorized under graphs, and assigned a medium difficulty level.

The goal of this problem is to merge a list of accounts based on their common email addresses, ensuring that each merged account includes the person's name and sorted email addresses.

Before we start, let's take a look at the problem statement:

Problem Statement:
You are given a list of accounts, where each account is represented as a list of strings.

The first element of each account is the person's name, while the rest of the elements are email addresses associated with that account.

Two accounts are considered to belong to the same person if they share at least one common email address.

Your task is to merge these accounts and return them in the required format.

Here's an example to illustrate the problem:

Example:

Input: accounts = [["John","[email protected]","[email protected]"],["John","[email protected]","[email protected]"],["Mary","[email protected]"],["John","[email protected]"]]
Output: [["John","[email protected]","[email protected]","[email protected]"],["Mary","[email protected]"],["John","[email protected]"]]

In this example, we have three distinct individuals: John, Mary, and Johny Bravo.

John has two email addresses, "[email protected]" and "[email protected]," and the same names are shared among the accounts.

John and Johny Bravo have no common email addresses, so they are treated as separate individuals.

Problem Overview

To solve this problem efficiently, we will use a Union-Find (Disjoint Set Union) data structure to group accounts that belong to the same person.

Here's the step-by-step approach:

Step 1: Initialize Union-Find Data Structure

We create a custom class UnionFind to implement the Union-Find data structure.

It helps us keep track of connected components, ensuring that accounts belonging to the same person are merged.

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [1] * n

    def find(self, x):
        while x != self.par[x]:
            self.par[x] = self.par[self.par[x]]
            x = self.par[x]
        return x

    def union(self, x1, x2):
        p1, p2 = self.find(x1), self.find(x2)
        if p1 == p2:
            return False
        if self.rank[p1] > self.rank[p2]:
            self.par[p2] = p1
            self.rank[p1] += self.rank[p2]
        else:
            self.par[p1] = p2
            self.rank[p2] += self.rank[p1]
        return True

Step 2: Create Data Structures

• We initialize a UnionFind data structure with the number of accounts.
• We create a dictionary emailToAcc to map email addresses to the account index they belong to.
• We create a dictionary emailGroup to store email groups for each leader account.

uf = UnionFind(len(accounts))
emailToAcc = {}  # email -> index of acc
emailGroup = defaultdict(list)  # index of acc -> list of emails

Step 3: Merge Accounts

We iterate through the list of accounts and email addresses, and for each email, we check if it exists in the emailToAcc dictionary.

If it does, we merge the accounts using the Union-Find data structure.

This step ensures that accounts with a common email address are connected.

Step 4: Create Email Groups

After merging accounts, we iterate through the emailToAcc dictionary to find the leader account for each email.

We use the leader account's index to map the email to the corresponding email group.

Step 5: Format Output

Finally, we format the output in the desired format.

For each leader account, we retrieve the person's name and their sorted email addresses, combining them into a single list.

res = []
for i, emails in emailGroup.items():
    name = accounts[i][0]
    res.append([name] + sorted(emailGroup[i]))  # array concatenation
return res

Time and Space Complexity

Time Complexity: O(n * m * log(n))

• n: The number of accounts.
• m: The maximum number of emails in a single account.

The time complexity is dominated by the Union-Find operations, specifically the find and union operations.

In the worst case, we may have to traverse a path of length log(n) for each email in each account.

Since there are n accounts, and each account may have m emails, the total time complexity is O(n * m * log(n)).

Space Complexity: O(n * m)

• n: The number of accounts.
• m: The maximum number of emails in a single account.

The space complexity is primarily due to the storage of email addresses in the emailToAcc and emailGroup dictionaries.

In the worst case, every email address may be unique, leading to O(n * m) space complexity.

Related Interview Questions By Company:

• Permutations LeetCode
• Validate Binary Search Tree LeetCode
• Number Of Connected Components In An Undirected Graph LeetCode

Related Interview Questions By Difficulty:

• Rotting Oranges LeetCode
• Redundant Connection LeetCode
• Accounts Merge LeetCode

Related Interview Questions By Category:

• Reverse Integer LeetCode
• Minimum Path Sum LeetCode
• Insert Into A Binary Search Tree LeetCode

Conclusion

In this blog post, we've explored the Accounts Merge problem from LeetCode, which involves merging accounts based on common email addresses while preserving the person's name and sorting the merged accounts.

We've implemented an efficient solution using a Union-Find data structure, followed by a step-by-step explanation of the solution's approach.

Solving this problem efficiently requires a good understanding of Union-Find data structures and graph-related algorithms.

We hope this post has helped you grasp the key concepts and strategies needed to tackle similar problems.

To practice and explore this problem further, you can visit the LeetCode problem page.

If you have any questions, comments, or suggestions, please feel free to share them in the comments section below.

Happy coding!