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

0% completed

Number of Provinces (medium)

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 directly connected to City C.

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

You are given a square matrix of size n x n, where each cell’s value indicates whether a direct connection between cities exists (1 for connected and 0 for not connected).

Determine the total number of provinces.


  • Example 1:
    • Input: [[1,1,0],[1,1,1],[0,1,1]]




Like the course? Get enrolled and start learning!