Accounts Merge | LeetCode | Solution Explained

LeetCode 721. Accounts Merge. I explain the solution in detail using the data structure: Disjoint Set Union or Union Find (DSU/UF). Problem Link.

0. Accounts Merge: Problem Discussion

0.0. IO Format

• Given: accounts = [[name1, email1, email2], [name2, email1, email2], ...]
• Goal: new_accounts
• Condition: If there’s a common email between two names, merge their email lists into one (sorted order)

0.1. Examples

Let x, y, z, a, p be unique emails. John, Mary, John and John look to be 4 different people.

But if you notice, John1 and John2 both share the common email, x. Thus, both are the same person.

1. Accounts Merge: Observations & Logic

1.0. Intuitions

So it looks like we have to merge two different names, sharing some common property – email.

If you have been following me for a while now, you’ll quickly realize that this hints at the use of Disjoint Set Union/Union Find (DSU/UF). It is a data structure that works well in cases when we need to unite two different sets which share some property.

1.1. DSU Format

Since the goal is to unite the names, we will create a DSU of names.

The only small issue is, how do we connect two names? We know it has to be through an email. So, we need to create some link from the email to the name.

This way, if we find some common email, we won’t unite the emails. Rather, we will unite the names.

1.2. Formalizing the logic

• The only time we need to take care about uniting two names is when the email has repeated. We can use a set or a dictionary for this. Using dictionary is better. Why? We can simultaneously also store the email –> name mapping.
• Once we know who all names are united, we can go through one intermediate state where we collect the emails belonging to a name.
• Finally, we can sort and return.

2. Accounts Merge: Optimized Implementation

2.0. Code

class DSU():
    def __init__(self, n):
        self.representatives = [i for i in range(n)]
        self.sizes = [1]*n
    
    def find(self, x):
        if self.representatives[x] == x: return x
        self.representatives[x] = self.find(self.representatives[x])
        return self.representatives[x]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        
        if x == y: return
        if self.sizes[x] > self.sizes[y]: x, y = y, x
        
        self.representatives[x] = y
        self.sizes[y] += self.sizes[x]

class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        n = len(accounts)
        dsu = DSU(n)
        
        email_to_name = {}
        for i, account in enumerate(accounts):
            for email in account[1:]:
                if email not in email_to_name:
                    email_to_name[email] = i
                else:
                    dsu.unite(i, email_to_name[email])
                    
        components = defaultdict(set)
        for email in email_to_name.keys():
            components[dsu.find(email_to_name[email])].add(email)
        
        ans = []
        for k, v in components.items():
            ans.append([accounts[k][0]] + sorted(list(v)))
        return ans

2.1. Complexity Analysis

• Time: O(NK.alpha(N) + NK log NK)
• Space: O(NK)

Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.