Number of Provinces — Day 89(Python)

Photo by Greg Rosenke on Unsplash

Today’s question is a frequently asked question among Amazon interviewers. Let us look into the problem statement.

547. Number of Provinces

There are cities. Some of them are connected, while some are not. If city is connected directly with the city , and city is connected directly with the city , then city is connected indirectly with city .

A province is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an matrix where if the city and the city is directly connected, and otherwise.

Return the total number of provinces.

Example 1:

Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output: 2

Example 2:

Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3

Constraints:

  • is or .

We are given a 2D matrix that is filled with 1s and 0s. The rows and the columns represent the cities. The ith city is connected to the jth city if the cell at matrix[i][j] is 1. All the connected cities create a province. We need to find the number of such provinces in our matrix.

Well, this question reminds the island problem that we solved earlier. You can follow this link in case you need a refresher.

Now, that we understand that the problem is similar to the island problem, let us solve this using DFS.

We would need a set that keeps track of all the visited cities. Next, we will traverse through each cell in our matrix, check if there is a link between the ith row and the jth column, and if the column has not been visited before. If the above conditions are satisfied, we will include the column in our visited set and then call our dfs function. In the dfs function, we will pass the column number.

for i in range(len(isConnected)):
for j in range(len(isConnected[0])):
if isConnected[i][j] == 1 and j not in visited:
visited.add(j)
dfs(j)
num += 1

When the dfs function is passed with the column number, this column will now act as the start point and look for cities that are connected to this column and again dfs function will be called until we do not have any connected cities to be traversed.

def dfs(start):
for k in range(len(isConnected[start])):
if isConnected[start][k] == 1 and k not in visited:
visited.add(k)
dfs(k)

Let us look at the complete code snippet.

class CircleNumFinder:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
visited = set()
num = 0
def dfs(start):
for k in range(len(isConnected[start])):
if isConnected[start][k] == 1 and k not in visited:
visited.add(k)
dfs(k)

for i in range(len(isConnected)):
for j in range(len(isConnected[0])):
if isConnected[i][j] == 1 and j not in visited:
visited.add(j)
dfs(j)
num += 1
return num

Another way to code this function is as below. We are avoiding duplicate calls by avoiding extra an loop.

class CircleNumFinder:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
visited = set()
num = 0
def dfs(start):
for k in range(len(isConnected[start])):
if isConnected[start][k] == 1 and k not in visited:
visited.add(k)
dfs(k)

for row in range(len(isConnected[0])):
if isConnected[row][row] == 1 and row not in visited:
visited.add(row)
dfs(row)
num += 1
return num

Complexity analysis.

Time Complexity

Since we are traversing through the entire matrix once, the time complexity is O(N²).

Space Complexity

Space complexity is O(N²) since we are storing all the cities in a set.

To solve the given question using BFS, using the following code snippet.

class CircleNumFinder:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
visited = set()
queue = []
num = 0
# Go through all the cities
for i in range(len(isConnected)):
#Check if it is visited earlier
if isConnected[i][i] == 1 and i not in visited:
queue.append(i)
visited.add(i)
num += 1
#Find its neighbors and indirectly connected cities
while(queue):
out = queue.pop(0)
for neigh in range(len(isConnected)):
if isConnected[out][neigh] == 1 and neigh not in visited:
queue.append(neigh)
visited.add(neigh)

return num

The time complexity and space complexity remains the same as DFS.

Software Engineer. Find me @ www.linkedin.com/in/annamariya-jt

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store