Search⌘ K
AI Features

DIY: Number of Provinces

Explore how to identify the total number of provinces from a matrix representing city connectivity. Learn to implement an algorithm that counts groups of directly or indirectly connected cities, preparing you for similar coding interview challenges.

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