Grokking Data Structures & Algorithms for Coding Interviews
Vote

0% completed

​

Problem 2: Number of Provinces (medium)

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 2 years ago

class UnionFind:
    def __init__(self):
        self.parents = {}
        self.rank = {}
        
    def find(self, u):
        parent = self.parents.get(u, u)
        if parent == u:
            self.parents[u] = u
            return self.parents[u]
        self.parents[u] = self.find(parent)
        return self.parents[u]

    def union(self, u, v):
        par_u = self.find(u)
        par_v = self.find(v)
        if par_u == par_v:
            return 
        if self.rank.get(par_u, 0) < self.rank.get(par_v, 0):
            self.parents[par_u] = par_v
        elif self.rank.get(par_v, 0) < self.rank.get(par_u, 0):
            self.parents[par_v] = par_u
        else:
            self.rank[par_u] = self.rank.get(par_u, 0) + 1
            self.parents[par_u] = par_v

class
A

Anonymous

· 3 years ago

The python solution uses path compression, but not union by rank. As a result, the complexity explanation is not clear. It says adding path compression and and union by rank get's it down to near n^2. So it's not clear what the complexity of the solution is (n^2, n^3, or something else), or if the solution could be improved by adding a union optimization. The ambiguity is confusing.

Reading Progress

0%

Vote for new content