Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Number of Provinces (medium)
On this page

Problem Statement

There are n cities. Some of them are connected in a network. If City A is directly connected to City B, and City B is directly connected to City C, city A is indirectly connected to City C.

If a group of cities are connected directly or indirectly, they form a province.

Given an n x n matrix isConnected where isConnected[i][j] = 1 if the i<sup>th</sup> city and the j<sup>th</sup> city are directly connected, and isConnected[i][j] = 0 otherwise, determine the total number of provinces.

Examples

  • Example 1:
    • Input: isConnected =

.....

.....

.....

Like the course? Get enrolled and start learning!

On this page