Number of Provinces

MediumGraphsunion find / dfs

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

There are n cities, labeled from 0 to n - 1. Some pairs of cities are directly connected by a road, and connectivity is transitive: if city a is connected to city b, and city b is connected to city c, then a and c belong to the same group even without a direct road between them. A **province** is a maximal group of cities such that every city in the group can reach every other city in the group, directly or indirectly, and no city outside the group is connected to it. You are given an n x n matrix isConnected, where isConnected[i][j] == 1 means city i and city j are directly connected, and isConnected[i][j] == 0 means they are not. The matrix is symmetric (isConnected[i][j] == isConnected[j][i]) and every city is connected to itself (isConnected[i][i] == 1). Return the total number of provinces.

Examples

Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]

Output: 2

Cities 0 and 1 are directly connected, forming one province. City 2 is isolated, forming a second province.

Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]

Output: 3

No two distinct cities are connected, so each of the 3 cities is its own province.

Input: isConnected = [[1,1,0,0],[1,1,0,0],[0,0,1,1],[0,0,1,1]]

Output: 2

Cities {0,1} form one province and cities {2,3} form another.

Constraints

`1 <= n <= 200`
`n == isConnected.length == isConnected[i].length`
`isConnected[i][j]` is `0` or `1`
`isConnected[i][i] == 1`
`isConnected[i][j] == isConnected[j][i]`

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.