FastPrepNumber of Provinces
Problems/Number of Provinces

Number of Provinces

PeopleStrong logoPeopleStrong● MediumFULLTIMEPHONE SCREEN

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in a PeopleStrong phone screen. The report names Number of Provinces. For this version, we chose to model the cities with a connection matrix. We also chose the function interface and the limits. Our version is about 90% the same as the reported question.

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[][]) → int

Examples

Example 1

connected = [[1,1,0],[1,1,0],[0,0,1]]return = 2

Cities 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 = 4

Every 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] and connected[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

Interview reports that mention this question

  • PeopleStrong SDE OA and Interview Questions: 12 Experiences
All PeopleStrong interview questionsSee PeopleStrong hiring insights
Saved
class Solution {
    public int countProvinces(int[][] connected) {
        // Write your solution here.
    }
}
Checking account…