DIY: Number of Provinces
Solve the interview question "Number of Provinces" in this lesson.
We'll cover the following
Problem statement
Suppose there are n
cities, where some are connected, while others are not.
If a city c1
is connected to city c2
, and city c2
is connected to city c3
, then c1
is indirectly connected to c3
.
A group of directly or indirectly connected cities, where no other city is part of this group, is called a province.
You are given a matrix, isConnected
with a size of n x n
. An entry isConnected[i][j] = 1
if the and cities are directly connected, and isConnected[i][j] = 0
otherwise. Note that isConnected[i][j]
is either 1
or 0
.
Your task is to return the total number of provinces.
Constrainsts
1 <= n <= 200
n == isConnected.length
n == isConnected[i].length
isConnected[i][i] == 1
isConnected[i][j] == isConnected[j][i]
Input
The input will be a list of lists representing a matrix. The following are examples of input to the function:
// Sample Input 1:
isConnected = [[1,1,0],[1,1,0],[0,0,1]]
// Sample Input 2:
isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Output
The output will be an integer. The following are examples of the outputs:
// Sample Output 1:
2
// Sample Output 2:
3
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.