Problem
There are n cities. You get an n x n matrix isConnected. isConnected[i][j] is 1 when a direct road connects city i and city j. Otherwise, it is 0.
Two cities are connected when a path of roads goes from one city to the other, directly or through other cities. A province is a group of connected cities that has no road to a city outside the group.
Return the number of provinces.
Example 1
- Input:
- isConnected = [[1,0,0,1],[0,1,1,0],[0,1,1,0],[1,0,0,1]]
- Output:
- 2
- Explanation:
- Cities 0 and 3 make one province. Cities 1 and 2 make the other province.
Example 2
- Input:
- isConnected = [[1,1,0],[1,1,1],[0,1,1]]
- Output:
- 1
- Explanation:
- City 0 and city 2 have no direct road, but both have a road to city 1.
Example 3
- Input:
- isConnected = [[1,0],[0,1]]
- Output:
- 2
Constraints
- 1 <= n <= 200
- n == isConnected.length
- n == isConnected[i].length
- isConnected[i][j] is 1 or 0.
- isConnected[i][i] == 1
- isConnected[i][j] == isConnected[j][i]
SysRound wrote this statement. A reference solution checks every example.
Related questions
Continue with questions that share topics or the same question type.
- Evaluate Division
Coding · Array · Bellman–Ford Algorithm · Breadth-First Search
- Minimize Malware Spread
Coding · Array · Breadth-First Search · Depth-First Search
- Possible Bipartition
Coding · Bipartite Graph · Breadth-First Search · Depth-First Search
- Number of Distinct Islands
Coding · Array · Breadth-First Search · Depth-First Search
Sources · 2 references
These records explain where the question appears. A company tag or candidate report does not guarantee a future interview question.
Hello Interview · 2 records
Amazon
Leetcode 547. Number of Provinces
Reported Nov 5, 2024 · 1 source report
MID_LEVEL
Source snapshot: Nov 12, 2026
View sourceCoupang
Leetcode 547. Number of Provinces
Reported Aug 13, 2026 · 1 source report
SENIOR
Source snapshot: Nov 12, 2026
View source
LeetCode company tags · 1 record
Uber
Number of Provinces
Reported date not specified · Source window: 6mo
Source snapshot: Oct 20, 2026
Source frequency score: 57.2. This is not an interview probability.
View source