Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Number of Provinces (medium)

Problem Statement

There are n cities. Some of them are connected in a network. If City A is directly connected to City B, and City B is directly connected to City C, city A is indirectly connected to City C.

If a group of cities are connected directly or indirectly, they form a province.

Given an n x n matrix isConnected where isConnected[i][j] = 1 if the i<sup>th</sup> city and the j<sup>th</sup> city are directly connected, and isConnected[i][j] = 0 otherwise, determine the total number of provinces.

Examples

  • Example 1:
    • Input: isConnected =

.....

.....

.....

Like the course? Get enrolled and start learning!
C

c.avina05

· 2 years ago

It's silly to hop into Union-Find at this level if you haven't been exposed to it.

Here is a simple DFS solution.

class Solution:
    def findProvinces(self, isConnected):
	    def dfs(node):
	      visited[node] = True
	      for neighbor in range(n):
		      if isConnected[node][neighbor] == 1 and not visited[neighbor]:
						dfs(neighbor)

			provinces = 0
			n = len(isConnected)
			visited = [False]*n
			for i in range(n):
				if not visited[i]:
					dfs(i)
					provinces += 1
		return provinces
L

Lee

· 2 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.

Mohammed Dh Abbas

Mohammed Dh Abbas

· 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
Cristian

Cristian

· 4 months ago

Is the union find solution wrong? Also, is the test results validator wrong?

Try this test case

[[1,0,0,1],[0,1,1,0],[0,1,1,0],[1,1,0,1]]

1 -> 4 -> 2 -> 3

Shouldn't it be 1 province?