How hard is LeetCode 721. Accounts Merge?

LeetCode 721. Accounts Merge is rated Medium on LeetCode.

What is the time complexity of LeetCode 721. Accounts Merge?

The Python solution on this page runs in O(n \times \log n).

What is the space complexity of LeetCode 721. Accounts Merge?

The Python solution on this page uses O(n) auxiliary space.

Accounts Merge — LeetCode 721 Python Solution

MediumDepth-First SearchBreadth-First SearchUnion FindArrayHash TableStringSorting

Problem: #721
Pattern: Union-Find
Reading time: 7 min
Source: leetcode.com

The problem

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. Now, we would like to merge these accounts.

Example

Input: accounts = [["John","johnsmith@mail.com","john_newyork@mail.com"],["John","johnsmith@mail.com","john00@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]
Output: [["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]
Explanation: The first and second John's are the same person as they have the common email "johnsmith@mail.com".

Python solution

Python

class UnionFind:
    def __init__(self, n):
        self.p = list(range(n))
        self.size = [1] * n

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, a, b):
        pa, pb = self.find(a), self.find(b)
        if pa == pb:
            return False
        if self.size[pa] > self.size[pb]:
            self.p[pb] = pa
            self.size[pa] += self.size[pb]
        else:
            self.p[pa] = pb
            self.size[pb] += self.size[pa]
        return True


class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        uf = UnionFind(len(accounts))
        d = {}
        for i, (_, *emails) in enumerate(accounts):
            for email in emails:
                if email in d:
                    uf.union(i, d[email])
                else:
                    d[email] = i
        g = defaultdict(set)
        for i, (_, *emails) in enumerate(accounts):
            root = uf.find(i)
            g[root].update(emails)
        return [[accounts[root][0]] + sorted(emails) for root, emails in g.items()]

Complexity

Measure	Complexity
Time	O(n \times \log n)
Space	O(n) auxiliary

Pattern: Union-Find

Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 721. Accounts Merge is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.

The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.

On a study list

This problem is on Grind 75.

Frequently asked questions

How hard is LeetCode 721. Accounts Merge?: LeetCode 721. Accounts Merge is rated Medium on LeetCode.
What is the time complexity of LeetCode 721. Accounts Merge?: The Python solution on this page runs in O(n \times \log n).
What is the space complexity of LeetCode 721. Accounts Merge?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 721. Accounts Merge cover?: LeetCode 721. Accounts Merge is tagged Depth-First Search, Breadth-First Search, Union Find, Array, Hash Table, String and Sorting on LeetCode.