Number of Provinces
Asked at Uber
Problem
Given an adjacency matrix representing connections between cities, find the number of connected components (provinces). Two cities are directly connected if the matrix value is 1, and transitively connected through other cities. This is the classic connected components problem in graph theory.
Asked At
| Company | Difficulty | |
|---|---|---|
| Uber | MEDIUM | View all Uber questions → |
How to Think About It
Model the problem as an undirected graph where matrix[i][j]=1 means an edge exists
Use DFS or BFS to traverse all nodes reachable from each unvisited starting node
Each unvisited node starts a new province, increment counter and explore all reachable nodes
Union-Find can solve this with path compression and union by rank
The answer equals the number of connected components in the graph
Optimal Approach
Treat the adjacency matrix as an undirected graph. Iterate through each city. If it has not been visited, start a DFS/BFS from it to mark all connected cities as visited, and increment the province count. The DFS explores all neighbors (where matrix[i][j]==1) recursively. Union-Find is an alternative: initialize each city as its own parent, then union cities that have an edge. The number of distinct roots equals the number of provinces.
What Trips People Up in Real Interviews
Clarify the matrix is symmetric since the graph is undirected
Confirm the diagonal is always 1 (each city connects to itself)
Mention DFS, BFS, and Union-Find all work with similar time complexity
Discuss that Union-Find is preferred when edges arrive as a stream
Note that the matrix representation is O(n²) space regardless of edge count
Solution Code
class Solution:
def findCircleNum(self, isConnected: list[list[int]]) -> int:
n = len(isConnected)
visited = set()
def dfs(node):
visited.add(node)
for neighbor in range(n):
if isConnected[node][neighbor] == 1 and neighbor not in visited:
dfs(neighbor)
provinces = 0
for city in range(n):
if city not in visited:
dfs(city)
provinces += 1
return provincesFrequently Asked Questions
What is the Number of Provinces problem?
Given an adjacency matrix representing connections between cities, find the number of connected components (provinces). Two cities are directly connected if the matrix value is 1, and transitively connected through other cities. This is the classic connected components problem in graph theory.
How do you solve Number of Provinces?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Number of Provinces?
Number of Provinces is asked at Uber. It is a medium difficulty problem.
What are common mistakes on Number of Provinces?
- Clarify the matrix is symmetric since the graph is undirected
- Confirm the diagonal is always 1 (each city connects to itself)
- Mention DFS, BFS, and Union-Find all work with similar time complexity
- Discuss that Union-Find is preferred when edges arrive as a stream
- Note that the matrix representation is O(n²) space regardless of edge count