Grokking the Coding Interview: Patterns for Coding Questions

Ask Author

Back to course home

0% completed

Solution: Number of Provinces

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.

Examples

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

.....

.....

.....

Like the course? Get enrolled and start learning!