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 n cities. Some of them are connected, while some are not. If city a is connected directly with the city b, and city b is connected directly with the city c, then city a is connected indirectly with city c.

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

You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city is directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of provinces.

Example 1:

Example 2:

Constraints:

  • 1 <= n <= 200
  • n == isConnected.length
  • n == isConnected[i].length
  • isConnected[i][j] is 1 or 0.
  • isConnected[i][i] == 1
  • isConnected[i][j] == isConnected[j][i]

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.

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.

Let us look at the complete code snippet.

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

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.

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

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