Watch 10 video solutions for Number of Provinces, a medium level problem involving Depth-First Search, Breadth-First Search, Union Find. This walkthrough by take U forward has 535,400 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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: 2
Example 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] is 1 or 0.isConnected[i][i] == 1isConnected[i][j] == isConnected[j][i]Problem Overview: You are given an n x n adjacency matrix isConnected where isConnected[i][j] = 1 means city i and city j are directly connected. A province is a group of cities connected directly or indirectly. The task is to count how many such provinces exist.
Approach 1: Depth-First Search (DFS) (Time: O(n2), Space: O(n))
Treat the matrix as a graph where each city is a node and isConnected[i][j] = 1 represents an undirected edge. Iterate through every city. When you encounter a city that hasn’t been visited, start a DFS traversal and mark all reachable cities as visited. That traversal covers exactly one connected component, which corresponds to a province. Since the adjacency matrix requires scanning all n neighbors for each node, the traversal costs O(n2). This approach directly applies classic Depth-First Search on a graph and is usually the most intuitive way to reason about connected components.
Approach 2: Union-Find (Disjoint Set) (Time: O(n2 · α(n)), Space: O(n))
Union-Find models each city as part of a disjoint set. Initially every city is its own parent. Scan the adjacency matrix and whenever isConnected[i][j] = 1, perform a union operation to merge the sets containing i and j. Path compression and union-by-rank keep operations nearly constant time, giving an amortized O(α(n)) cost per union. After processing the matrix, the number of unique roots represents the number of provinces. This approach works well when you repeatedly merge components or when connectivity queries appear in larger systems using Union Find.
Recommended for interviews: DFS (or BFS) is the most expected explanation because the problem maps directly to counting connected components in a graph. Interviewers want to see that you recognize the adjacency matrix as a graph representation and run a traversal to mark visited nodes. Union-Find is equally valid and demonstrates deeper familiarity with graph connectivity techniques. Start with DFS to show clear reasoning, then mention Union-Find as an alternative optimization pattern.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Depth-First Search (DFS) | O(n^2) | O(n) | Best general solution when treating the matrix as a graph and counting connected components. |
| Union-Find (Disjoint Set) | O(n^2 · α(n)) | O(n) | Useful when repeatedly merging components or solving dynamic connectivity problems. |