Number of Provinces
Last Updated: March 28, 2026
Understanding the Problem
This problem is really about counting connected components in an undirected graph. Each city is a node, and isConnected[i][j] = 1 means there's an edge between node i and node j. A "province" is just another word for a connected component, a maximal set of nodes where you can reach any node from any other node through some path.
The adjacency matrix representation is important here. Unlike an adjacency list where you directly see each node's neighbors, the matrix has n x n entries. For any city i, you find its neighbors by scanning row i and looking for all columns j where isConnected[i][j] = 1 (excluding j = i, since every city is trivially connected to itself).
The core question is: how many separate groups of cities exist? If you start at any unvisited city and explore all reachable cities from there, you've found one complete province. The number of times you need to start a fresh exploration equals the number of provinces.
Key Constraints:
1 <= n <= 200→ With n up to 200, the matrix has at most 40,000 entries. O(n^2) is perfectly fine, and even O(n^3) would pass comfortably.isConnected[i][j] == isConnected[j][i]→ The graph is undirected. We don't need to worry about directed edges.isConnected[i][i] == 1→ Every city is connected to itself. This is just a property of the matrix, not a useful edge.
Approach 1: DFS (Depth-First Search)
Intuition
The most natural way to think about this problem: start at a city you haven't visited, and explore as far as you can, visiting every city reachable from it. Once you can't reach any more new cities, you've found one complete province. Then look for the next unvisited city and repeat. The number of times you start a fresh DFS traversal is exactly the number of provinces.
This is the classic connected components algorithm. The visited array prevents us from counting the same city twice, and the DFS ensures we reach every city in the current component before moving on.
Algorithm
- Create a
visitedboolean array of sizen, initialized tofalse. - Initialize
provinces = 0. - For each city
ifrom0ton - 1: - If city
ihas not been visited, start a DFS from cityiand incrementprovinces. - The DFS marks city
ias visited, then recursively visits all unvisited neighbors ofi. - To find neighbors of city
i, scan rowiof the matrix: cityjis a neighbor ifisConnected[i][j] == 1andj != i. - Return
provinces.
Example Walkthrough
Code
- Time Complexity: O(n^2). We visit each city once, and for each city we scan its entire row (n entries) to find neighbors. Total work across all DFS calls is O(n^2).
- Space Complexity: O(n). The visited array takes O(n) space. The recursion stack can go up to O(n) deep in the worst case.
DFS uses recursion, which risks a stack overflow for deep graphs. Can we solve this iteratively instead?
Approach 2: BFS (Breadth-First Search)
Intuition
BFS is an iterative alternative to DFS that avoids recursion entirely. Instead of diving deep into one path, we use a queue to explore all neighbors of the current city before moving to the next level. The result is identical: we find all cities in the same province, one component at a time.
The advantage over DFS is purely practical. BFS uses an explicit queue instead of the call stack, so we don't risk a stack overflow on deep graphs.
BFS and DFS both find all nodes reachable from a starting node. The difference is just the order of exploration. DFS goes deep first, while BFS explores level by level. For counting connected components, the exploration order doesn't matter. What matters is that every reachable node gets marked as visited, and that's guaranteed by both approaches.
Algorithm
- Create a
visitedboolean array of sizen, initialized tofalse. - Initialize
provinces = 0. - For each city
ifrom0ton - 1: - If city
ihas not been visited, start a BFS from cityiand incrementprovinces. - BFS: add
ito a queue, mark it visited. While the queue is not empty, dequeue a city, scan its row for unvisited neighbors, and enqueue them. - Return
provinces.
Example Walkthrough
Code
- Time Complexity: O(n^2). Same as DFS. We visit each city once, and for each city we scan its entire row (n entries) to find neighbors.
- Space Complexity: O(n). The visited array is O(n). The queue can hold at most n cities in the worst case.
Both DFS and BFS require graph traversal. What if we could solve this by incrementally merging connected cities into groups, without any traversal at all?
Approach 3: Union Find
Intuition
Union Find (also called Disjoint Set Union) takes a completely different angle. Instead of traversing the graph to discover components, we process each edge and merge the two cities it connects into the same set. At the end, the number of distinct sets equals the number of provinces.
The idea is simple. Start with each city in its own set (n sets total). For each connection isConnected[i][j] = 1, merge the sets containing city i and city j. Each merge reduces the count of distinct sets by 1 (unless they're already in the same set). After processing all connections, the remaining number of sets is the answer.
Path compression and union by rank are two standard optimizations that keep the operations nearly O(1) amortized.
Algorithm
- Initialize a
parentarray whereparent[i] = i(each city is its own root). - Initialize a
rankarray of all zeros (used for union by rank). - Set
provinces = n(initially each city is its own province). - For each pair
(i, j)wherei < jandisConnected[i][j] == 1: - Find the root of city
iand cityj. - If the roots are different, merge them (union) and decrement
provinces. - Return
provinces.
Example Walkthrough
Code
- Time Complexity: O(n^2 * alpha(n)). We iterate over the upper triangle of the matrix (O(n^2) iterations). Each union/find operation takes O(alpha(n)) amortized, which is effectively constant.
- Space Complexity: O(n). The parent and rank arrays each take O(n) space.