DIY: Number of Provinces

Solve the interview question "Number of Provinces" in this lesson.

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 ithi^{th} and jthj^{th} 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.


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


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]]


The output will be an integer. The following are examples of the outputs:

// Sample Output 1:

// Sample Output 2:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.