Number of Provinces

Try to solve the Number of Provinces problem.


Let’s say we have nn number of cities, and some of them are connected, while some are not. If a city A is connected directly with city B, and city B is connected directly with city C, then we can say that city A is connected indirectly with city C.

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

An (n×n)(n \times n) matrix, isCityConnected, is given, where isCityConnected[i][j] = 1 indicates that the ithi^{th} and the jthj^{th} cities are directly connected. Otherwise, the value is isCityConnected[i][j] = 0.

Use this information to return the total number of provinces.


  • 1n2001 \leq n \leq 200

  • n==n == isCityConnected.length

  • n==n == isCityConnected[i].length, where 0in0 \leq i \leq n

  • isCityConnected[i][j] is 11 or 00.

  • isCityConnected[i][i] ==1== 1

  • isCityConnected[i][j] ==== isCityConnected[j][i]


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