Number of Provinces
Problem Statement
There are n cities. You are given an n x n matrix isConnected where isConnected[i][j] = 1 means city i and city j are directly connected, and 0 means they are not directly connected.
A province is a group of directly or indirectly connected cities with no connection to cities outside the group. Return the total number of provinces.
Input
A symmetric adjacency matrix isConnected. Row i tells you which cities are directly connected to city i.
Output
An integer: the number of provinces, which is the number of connected components among the cities.
Constraints
- •
n == isConnected.length - •
n == isConnected[i].length - •
1 <= n <= 200 - •
isConnected[i][j] is 0 or 1 - •
isConnected[i][i] == 1 - •
isConnected[i][j] == isConnected[j][i]
Examples
Example 1
isConnected = [[1,1,0],[1,1,0],[0,0,1]]
2Example 2
isConnected = [[1,0,0],[0,1,0],[0,0,1]]
3Learning Objectives
- Translate an adjacency matrix into the same connected-components idea from an edge list.
- Traverse directly over matrix rows instead of first building adjacency lists.
- Use Union-Find over the upper triangle of a symmetric matrix to avoid duplicate work.
- Explain why direct and indirect connections belong to the same province.
Intuition
This is the same question as counting connected components, but the representation changed. Problem 1 gave you an edge list: only existing edges were listed. Here you get an adjacency matrix: for a city i, every column j answers whether i has a direct road to j. That means finding neighbours costs a scan across row i.
The province definition is transitive. If 0 is connected to 1 and 1 is connected to 2, then all three cities belong to one province even if isConnected[0][2] is 0. A DFS captures that naturally: starting from one unvisited city, scan its row, recursively visit every directly connected city, and let those cities reveal indirect connections through their own rows.
Union-Find tells the same story through merges. Because the matrix is symmetric and the diagonal is always 1, you only need to inspect the upper triangle where j > i. Every 1 there is one undirected edge. Union those endpoints and count successful merges from an initial n provinces.
Recognise the distinction: edge-list problems are O(E) to scan; matrix problems are usually O(n²) because every possible city pair is present as a matrix cell.
Common mistakes
- ×Treating isConnected as a list of edges instead of a square matrix and indexing it incorrectly.
- ×Counting only direct neighbours of city 0 rather than transitive reachability through intermediate cities.
- ×Scanning both matrix triangles and then decrementing province count without checking whether union actually merged two sets.
- ×Forgetting that isConnected[i][i] is 1 by definition and should not create a new province or special case.
- ×Building an adjacency list unnecessarily; it works, but the matrix can be traversed directly.
Algorithm Explanation
DFS over the matrix: keep a visited array. Scan cities 0..n-1; each unvisited city starts a new province. DFS marks the city and scans all possible neighbours in its row. For every connected and unvisited neighbour, recurse.
Union-Find over the upper triangle: initialise n singleton sets. For each pair (i, j) with j > i, if isConnected[i][j] == 1, union i and j. Decrement the province count only when union returns true. Return the final count.
Solutions
Solution 1: DFS over the adjacency matrix
Best first answer for this exact input shape. The matrix is already built, n is small enough for recursion, and DFS maps directly to the province definition.
Scan every city. When you find one that has not been visited, it is the first city of a new province. DFS from it by scanning its matrix row and visiting every connected unvisited city.
Step-by-step
- Create visited[n] and provinces = 0.
- For each city, if visited[city] is false, increment provinces and call dfs(city).
- dfs(city) marks the city visited, then scans neighbour = 0..n-1.
- If isConnected[city][neighbor] == 1 and neighbour is unvisited, recurse into neighbour.
- One DFS marks one whole province, including indirect connections.
O(n²)
O(n)
Each DFS row scan costs O(n), and every city is visited once; recursion depth is O(n).
Java implementation
Solution 2: Union-Find over the upper triangle
Useful when you want the same component-counting template as edge-list problems, or when the interviewer pivots to dynamic additions of city connections.
Read each matrix 1 above the diagonal as an undirected edge and union its two cities. The diagonal and lower triangle do not add new information.
Step-by-step
- Start with provinces = n and each city as its own parent.
- For every i, inspect j from i + 1 to n - 1.
- When isConnected[i][j] == 1, union i and j.
- If the union merged two previously separate roots, decrement provinces.
- Return provinces after all possible pairs have been considered.
O(n² · α(n))
O(n)
The matrix scan dominates; Union-Find operations are effectively constant amortised time.
Java implementation
Dry Run
Sample input
isConnected = [[1,1,0,0],[1,1,0,0],[0,0,1,1],[0,0,1,1]]. DFS scans cities in order.
| Scan city | Visited before | Action | Provinces |
|---|---|---|---|
| 0 | none | New province; DFS visits 0 then 1 | 1 |
| 1 | 0,1 | Already visited through city 0 | 1 |
| 2 | 0,1 | New province; DFS visits 2 then 3 | 2 |
| 3 | 0,1,2,3 | Already visited through city 2 | 2 |
| done | all cities | Return province count | 2 |
The outer scan starts exactly two DFS traversals: one for cities {0,1} and one for cities {2,3}. Therefore the matrix contains 2 provinces.
Interview Tips
Call out the representation difference immediately: this is not an edge list, so a neighbour lookup is a row scan. That prevents many off-by-one and shape mistakes. For the DFS answer, emphasise transitive connectivity; for the Union-Find answer, mention scanning only the upper triangle because the matrix is symmetric. If asked for production-scale behaviour, note that a sparse graph should not be stored as an n x n matrix because O(n²) space is wasteful.
Likely follow-ups
- Return the cities in each province as groups.
- The matrix is sparse and huge; how would you store and traverse it more efficiently?
- Connections are added over time and you must update the province count after each addition.
- What changes if the matrix is directed rather than symmetric?
Similar Problems
Key Takeaways
- A province is just a connected component under a city graph.
- Adjacency matrices make neighbour discovery an O(n) row scan.
- For symmetric matrices, the upper triangle contains every undirected edge exactly once.
- Transitive connectivity matters: direct links can pull indirect cities into the same province.