Number of Provinces
Updated
Problem statement
Given an n × n matrix connected describing direct connections between cities, return the number of provinces. A province contains a city and every city you can reach from it, either directly or through other cities.
For this exercise, assume connections are undirected: connected[i][j] = 1 exactly when cities i and j have a direct connection, the matrix is symmetric, and every diagonal entry is 1. An isolated city is a province by itself.
Function
countProvinces(connected: int[][]) → intExamples
Example 1
connected = [[1,1,0],[1,1,0],[0,0,1]]return = 2Cities 0 and 1 form one province. City 2 is isolated and forms another.
Example 2
connected = [[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]]return = 4Every city is isolated, so each contributes one province.
Constraints
- For this exercise, assume
1 <= n <= 100, with every row containing n entries. - Every entry is 0 or 1.
connected[i][j] == connected[j][i]andconnected[i][i] == 1.
More PeopleStrong Phone Screen questions
- Reverse Linked-List Nodes in Groups of KOA · PHONE SCREEN · Seen Mar 2026
- Level of the Minimum-Sum SubtreePHONE SCREEN · Seen Jan 2026
- Ceiling Value in a Sorted ArrayPHONE SCREEN · Seen Sep 2025
- Maximum Employee Salary for a CompanyPHONE SCREEN · Seen Sep 2025
- Valid ParenthesesPHONE SCREEN · Seen Sep 2025
- Shortest Subarray with an Exact Target SumPHONE SCREEN · Seen May 2025
- Add Forward Linked-List Numbers Using RecursionPHONE SCREEN · Seen Oct 2021
- Running Median of a StreamPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2021
- Build an Expression Tree from PostfixPHONE SCREEN · Seen Oct 2021
- Maximum Score from Deleting Neighboring ValuesPHONE SCREEN · Seen Oct 2021
Similar questions at other companies
- Number of IslandsAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Task Build Order and File-Change RerunsVanta · PHONE SCREEN
- All Halfway Courses Across Course TracksCrunchyroll · PHONE SCREENCrunchyroll interview questions
- Course Schedule Cycle DetectionGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Resolve Variable Equations with Dependency ErrorsApplied Intuition · PHONE SCREENApplied Intuition interview questions
- Evaluate DivisionApple · PHONE SCREENApple interview questions
- Nested Substitutions with Cycle DetectionKikoff · PHONE SCREENKikoff interview questions
- Filter Undesired Comments and Their DescendantsReddit · PHONE SCREEN · ONSITE INTERVIEWReddit interview questions
- Validate and Resolve Evaluation ChainsPlaid · PHONE SCREEN · ONSITE INTERVIEWPlaid interview questions
- Count Groups of Diseased PlantsYellow.ai · PHONE SCREEN