Number of Provinces
MedPrompt
There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.
A province is a group of directly or indirectly connected cities and no other cities outside of the group.
You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.
Return the total number of provinces.
Example 1:
Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output: 2Example 2:
Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3
Constraints:
1 <= n <= 200n == isConnected.lengthn == isConnected[i].lengthisConnected[i][j]is1or0.isConnected[i][i] == 1isConnected[i][j] == isConnected[j][i]
Approaches
3 approaches with complexity analysis and trade-offs.
The Union-Find data structure, also known as Disjoint Set Union (DSU), is highly efficient for problems that involve partitioning a set of elements into a number of disjoint, non-overlapping subsets. This problem fits perfectly, as a province is a set of connected cities. We can treat each city as an element. If two cities are connected, we merge their sets. The final number of disjoint sets gives us the number of provinces.
Algorithm
- Create a Union-Find (or Disjoint Set Union) data structure initialized with
nsets, one for each city. The number of provinces is initiallyn. - The data structure should support
find(with path compression) andunion(with union by rank/size) operations. - Iterate through the adjacency matrix
isConnected. Since the matrix is symmetric, we only need to traverse the upper or lower triangle to avoid redundant checks. - For each pair of cities
(i, j)wherei < jandisConnected[i][j] == 1, perform aunion(i, j)operation. - The
union(i, j)operation will merge the sets containingiandjif they are not already in the same set. If a merge occurs, decrement the province count. - After iterating through all connections, the remaining count of disjoint sets is the total number of provinces.
Walkthrough
We initialize a DSU data structure for n cities, where each city is initially in its own set. This means we start with n provinces. We use a parent array to track the representative of each set and a rank array to optimize the union operations (union by rank). We then iterate through the isConnected matrix. For every direct connection found between two cities i and j, we call the union operation on them.
The union(i, j) operation finds the representatives of the sets for i and j. If they are different, it merges the two sets and decrements the total province count. To make the find operation faster, we use path compression, which flattens the structure of the trees representing the sets.
After checking all pairs of cities, the final value of our province counter is the answer.
class Solution { public int findCircleNum(int[][] isConnected) { int n = isConnected.length; UnionFind uf = new UnionFind(n); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (isConnected[i][j] == 1) { uf.union(i, j); } } } return uf.getCount(); }} class UnionFind { private int[] parent; private int[] rank; private int count; public UnionFind(int n) { count = n; parent = new int[n]; rank = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; rank[i] = 0; } } public int find(int i) { if (parent[i] != i) { parent[i] = find(parent[i]); // Path compression } return parent[i]; } public void union(int i, int j) { int rootI = find(i); int rootJ = find(j); if (rootI != rootJ) { // Union by rank if (rank[rootI] > rank[rootJ]) { parent[rootJ] = rootI; } else if (rank[rootI] < rank[rootJ]) { parent[rootI] = rootJ; } else { parent[rootJ] = rootI; rank[rootI]++; } count--; } } public int getCount() { return count; }}Complexity
Time
O(n^2 * α(n)) - We iterate through the `n x n` matrix, which takes O(n^2) time. Each `union` operation takes nearly constant time, O(α(n)), where α(n) is the inverse Ackermann function. The total time is dominated by the matrix traversal.
Space
O(n) - We need a `parent` array and a `rank` array, both of size `n`.
Trade-offs
Pros
Extremely efficient and a standard tool for connectivity problems.
The Union-Find data structure is versatile and applicable to a wide range of other problems (e.g., Kruskal's algorithm, cycle detection).
Cons
The implementation is more complex compared to a standard graph traversal like DFS or BFS.
The time complexity has an extra
α(n)factor, making it slightly slower in theory than a pure O(n^2) traversal for an adjacency matrix representation, although this factor is negligible in practice.
This approach models the problem as finding the number of connected components in a graph. We can traverse the graph using Breadth-First Search (BFS). We iterate through each city. If a city hasn't been visited, it marks the beginning of a new province. We then start a BFS from this city to find and mark all cities belonging to the same province. The total number of times we initiate a BFS on an unvisited node gives us the number of provinces.
Algorithm
- Initialize a
visitedboolean array of sizento keep track of visited cities. - Initialize a
provincescounter to 0. - Iterate through each city
ifrom0ton-1. - If city
ihas not been visited:- Increment
provincescount. - Start a Breadth-First Search (BFS) from city
ito find all connected cities.
- Increment
- The BFS traversal from a starting city
s:- Create a queue and add
sto it. - Mark
sas visited. - While the queue is not empty:
- Dequeue a city
u. - For each city
v, check ifuandvare connected and ifvhas not been visited. - If so, mark
vas visited and enqueue it.
- Dequeue a city
- Create a queue and add
- After the loop finishes, return the
provincescount.
Walkthrough
We use a boolean array visited to keep track of cities that have already been assigned to a province. We loop through all the cities from 0 to n-1. If we encounter an unvisited city i, we know it's part of a new province, so we increment our province counter.
Then, we use BFS to find all cities connected to i. BFS is an iterative approach that uses a queue. We add city i to the queue and mark it as visited. Then, as long as the queue is not empty, we dequeue a city, check all its direct connections, and for any unvisited connected city, we mark it as visited and add it to the queue. This process ensures that all cities reachable from i are visited.
By the time the queue is empty, we have explored the entire province. We then continue our main loop to find the next unvisited city, which would belong to another province.
import java.util.Queue;import java.util.LinkedList; class Solution { public int findCircleNum(int[][] isConnected) { int n = isConnected.length; boolean[] visited = new boolean[n]; int provinces = 0; Queue<Integer> queue = new LinkedList<>(); for (int i = 0; i < n; i++) { if (!visited[i]) { provinces++; queue.add(i); visited[i] = true; while (!queue.isEmpty()) { int u = queue.poll(); for (int v = 0; v < n; v++) { if (isConnected[u][v] == 1 && !visited[v]) { visited[v] = true; queue.add(v); } } } } } return provinces; }}Complexity
Time
O(n^2) - Each city is enqueued and dequeued exactly once. For each city, we iterate through its row in the adjacency matrix, which takes O(n) time. Thus, the total time complexity is O(n^2).
Space
O(n) - The `visited` array requires O(n) space. The queue can hold up to O(n) cities in the worst case.
Trade-offs
Pros
It's an iterative approach, which avoids the risk of stack overflow that can occur with deep recursion in DFS.
Conceptually simple and a fundamental graph traversal algorithm.
Cons
BFS might have slightly more overhead due to queue management compared to a recursive DFS, though this is often negligible.
The problem of finding provinces is equivalent to finding the number of connected components in a graph. The cities can be seen as vertices and the connections as edges. A straightforward way to solve this is by using a graph traversal algorithm like Depth-First Search (DFS). We iterate through each city, and if it hasn't been visited yet, we start a DFS from it to find all connected cities, marking them as visited. Each time we start a new DFS on an unvisited node, we've found a new province.
Algorithm
- Initialize a
visitedboolean array of sizento allfalse. - Initialize a
provincescounter to 0. - Iterate through each city
ifrom0ton-1. - If
visited[i]isfalse:- Increment
provinces. - Call a recursive DFS function
dfs(i)to explore its entire connected component.
- Increment
- The
dfs(u)function:- Mark the current city
uas visited. - Iterate through all other cities
v. - If
uandvare connected (isConnected[u][v] == 1) andvhas not been visited, make a recursive calldfs(v).
- Mark the current city
- Return the final
provincescount.
Walkthrough
The core of this approach is a visited array and a counter for provinces. We iterate through all cities from 0 to n-1. If we find a city i that has not been visited, we've discovered a new province. We increment our province counter and then start a DFS from city i.
The DFS is a recursive function that explores a graph as far as possible along each branch before backtracking. When we call dfs(u), we first mark city u as visited. Then, we look at its row in the isConnected matrix. For every city v that is connected to u and has not been visited, we make a recursive call dfs(v). This process continues until all cities in the same connected component (province) as i have been visited.
After the DFS for one component is complete, the main loop continues, searching for the next unvisited city, which will be the starting point of the next province.
class Solution { public int findCircleNum(int[][] isConnected) { int n = isConnected.length; boolean[] visited = new boolean[n]; int provinces = 0; for (int i = 0; i < n; i++) { if (!visited[i]) { provinces++; dfs(i, isConnected, visited); } } return provinces; } private void dfs(int u, int[][] isConnected, boolean[] visited) { visited[u] = true; for (int v = 0; v < isConnected.length; v++) { if (isConnected[u][v] == 1 && !visited[v]) { dfs(v, isConnected, visited); } } }}Complexity
Time
O(n^2) - We visit every cell of the `n x n` adjacency matrix at most once. The `dfs` function is called for each city. Inside `dfs`, we loop `n` times. Since we only enter the recursive call for unvisited cities, each city is processed once, leading to a total complexity proportional to the size of the matrix.
Space
O(n) - The `visited` array requires O(n) space. The recursion call stack can go up to `n` deep in the worst-case scenario (a path-like graph).
Trade-offs
Pros
Intuitive and easy to implement using recursion.
The code is often more compact than an iterative BFS.
It is a very efficient and standard way to find connected components.
Cons
For very deep graphs, the recursion could lead to a stack overflow error. However, with the given constraint of
n <= 200, this is not a concern.
Solutions
Solution
class Solution { private int [][] g ; private boolean [] vis ; public int findCircleNum ( int [][] isConnected ) { g = isConnected ; int n = g . length ; vis = new boolean [ n ]; int ans = 0 ; for ( int i = 0 ; i < n ; ++ i ) { if (! vis [ i ]) { dfs ( i ); ++ ans ; } } return ans ; } private void dfs ( int i ) { vis [ i ] = true ; for ( int j = 0 ; j < g . length ; ++ j ) { if (! vis [ j ] && g [ i ][ j ] == 1 ) { dfs ( j ); } } } }class Solution { public: int findCircleNum ( vector < vector < int >>& isConnected ) { int n = isConnected . size (); int ans = 0 ; bool vis [ n ]; memset ( vis , false , sizeof ( vis )); function < void ( int ) > dfs = [ & ]( int i ) { vis [ i ] = true ; for ( int j = 0 ; j < n ; ++ j ) { if ( ! vis [ j ] && isConnected [ i ][ j ]) { dfs ( j ); } } }; for ( int i = 0 ; i < n ; ++ i ) { if ( ! vis [ i ]) { dfs ( i ); ++ ans ; } } return ans ; } };class Solution : def findCircleNum ( self , isConnected : List [ List [ int ]]) -> int : def dfs ( i : int ): vis [ i ] = True for j , x in enumerate ( isConnected [ i ]): if not vis [ j ] and x : dfs ( j ) n = len ( isConnected ) vis = [ False ] * n ans = 0 for i in range ( n ): if not vis [ i ]: dfs ( i ) ans += 1 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.