Number of Provinces
Problem
Given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and 0 otherwise, return the total number of provinces (groups of directly or indirectly connected cities).
- 1 ≤ n ≤ 200
- isConnected.length == n
- isConnected[i].length == n
- isConnected[i][j] is 0 or 1
- isConnected[i][i] == 1
- isConnected[i][j] == isConnected[j][i]
Example
isConnected = [[1,1,0],[1,1,0],[0,0,1]]2The cities 0 and 1 are directly connected, forming one province. City 2 is isolated, forming a second province. The DFS starts at city 0, marks city 1 as visited through the connection, and completes the first province. Then it moves to city 2, which is unvisited, marking the second province. The total count is 2.
Approach
Straightforward Solution
A brute-force approach would check every pair of cities and attempt to group them, but without efficient traversal, this leads to redundant checks and higher complexity.
Core Observation
The problem reduces to counting connected components in an undirected graph represented by an adjacency matrix. Each city is a node, and edges exist where isConnected[i][j] == 1.
Path to Optimal
PreviewRecognizing the problem as connected components counting suggests graph traversal algorithms. DFS or BFS can explore all nodes reachable from a starting node, marking them visited…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewIterate over each city. If it is unvisited, increment the province count and perform a DFS to mark all cities connected to it as visited…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n^2)
The adjacency matrix has n^2 entries. The DFS explores each node and its neighbors once, resulting in O(n^2) time since each edge is checked via the matrix.
Space
O(n)
The auxiliary space is O(n) for the recursion stack in the worst case and the visited set storing up to n nodes.
Pattern Spotlight
DFS (Connected Components in Graph)
When counting groups of connected nodes in an undirected graph, use DFS to explore and mark all nodes in a component starting from any unvisited node, incrementing the count each time a new unvisited node is found.
Solution
| 1 | class Solution:
|
| 2 | def findCircleNum(self, isConnected: List[List[int]]) -> int:
|
| 3 | n = len(isConnected)
|
| 4 | seen = set()
|
| 5 |
|
| 6 | def dfs(i):
|
| 7 | for j in range(n):
|
| 8 | if isConnected[i][j] == 1 and j not in seen:
|
| 9 | seen.add(j)
|
| 10 | dfs(j)
|
| 11 |
|
| 12 | provinces = 0
|
| 13 | for i in range(n):
|
| 14 | if i not in seen:
|
| 15 | provinces += 1
|
| 16 | seen.add(i)
|
| 17 | dfs(i)
|
| 18 |
|
| 19 | return provinces |
Step-by-Step Solution
Initialize Variables and Define DFS Traversal
| 3 | n = len(isConnected)
|
| 4 | seen = set()
|
| 6 | def dfs(i):
|
| 7 | for j in range(n):
|
| 8 | if isConnected[i][j] == 1 and j not in seen:
|
| 9 | seen.add(j)
|
| 10 | dfs(j)
|
Objective
To prepare the data structures needed for traversal and define the recursive DFS function to explore connected cities.
Key Insight
Storing visited cities in a set prevents revisiting and infinite loops. The DFS function systematically explores all neighbors of a city, recursively marking connected cities as visited. This encapsulates the core traversal logic, enabling efficient connected component detection.
Interview Quick-Check
Core Logic
The DFS function recursively visits all cities connected to the current city, marking them visited to avoid repeated processing.
State & Boundaries
The visited set tracks which cities have been explored, ensuring each city is processed once.
Common Pitfalls & Bugs
Forgetting to add a city to the visited set before recursive DFS calls can cause infinite recursion or repeated visits.
Count Provinces by Iterating Over Cities and Invoking DFS
To iterate through all cities, identify unvisited ones, increment the province count, and trigger DFS to mark all connected cities.
Return the Total Number of Provinces
To output the final count of provinces after all cities have been processed.
2 more steps with full analysis available on Pro.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
if isConnected[i][j] == 1 and j not in seen:Check if the neighbor city is connected and unvisited.
This conditional is critical because it ensures the DFS only explores valid, unvisited neighbors, preventing cycles and redundant traversals.
seen.add(j)Mark the neighbor city as visited.
Marking a city as visited before recursive calls is essential to avoid revisiting the same city multiple times, which would cause infinite recursion or incorrect province counts.
seen.add(i)Mark the current city as visited before DFS.
Adding the city to visited before DFS is critical to avoid infinite recursion and to correctly identify the province's extent.
Full line-by-line criticality + rationale for all 14 lines available on Pro.
Test Your Understanding
Why does performing a DFS from each unvisited city correctly count the number of provinces?
See the answer with Pro.
Related Problems
DFS pattern
Don't just read it. Drill it.
Reconstruct Number of Provinces from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Number of Provinces drill