Number of Provinces
Problem link: https://leetcode.com/problems/number-of-provinces/
Problem Statement
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 indirectly connected with city c.
A province is a group of directly or indirectly connected cities.
You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and jth city are directly connected, and 0 otherwise.
Return the total number of provinces.
Input
- isConnected: n x n adjacency matrix
- isConnected[i][j] = 1 means connection
Output
- Return number of connected components (provinces)
Example
isConnected = [
[1,1,0],
[1,1,0],
[0,0,1]
]
Explanation
Cities 0 and 1 are connected → 1 province City 2 is isolated → another province
Total = 2
Brute Force
Intuition
Treat each city as a node. For every unvisited city, explore all reachable cities using DFS/BFS. Each traversal gives one province.
Approach
- Maintain visited array
- Loop through each city
- If not visited → start DFS
- Mark all reachable cities
- Increment province count
Dry Run
Input: [[1,1,0],[1,1,0],[0,0,1]]
Step 1: Start at city 0 → not visited → DFS(0) → Visit 1 → Both marked visited → Province count = 1
Step 2: City 1 already visited → skip
Step 3: City 2 not visited → DFS(2) → Only itself → Province count = 2
Final Answer = 2
Visualization
Code (Java)
class Solution {
public int findCircleNum(int[][] isConnected) {
int n = isConnected.length;
boolean[] visited = new boolean[n];
int count = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
dfs(isConnected, visited, i);
count++;
}
}
return count;
}
private void dfs(int[][] graph, boolean[] visited, int node) {
visited[node] = true;
for (int j = 0; j < graph.length; j++) {
if (graph[node][j] == 1 && !visited[j]) {
dfs(graph, visited, j);
}
}
}
}
Complexity Analysis
We traverse adjacency matrix → O(N^2). DFS stack → O(N).
Optimal Solution
Intuition
Use Disjoint Set (Union-Find) to group connected cities. Each connected component forms a province.
Approach
- Initialize parent array
- For each connection, union nodes
- Count unique parents
Dry Run
Input: [[1,1,0],[1,1,0],[0,0,1]]
Step 1: Initially → parent = [0,1,2]
Step 2: Check connections
- (0,1) → union → parent becomes same
Step 3: Final parents → [0,0,2]
Step 4: Unique parents → {0,2}
Answer = 2
Visualization
Code (Java)
class Solution {
public int findCircleNum(int[][] isConnected) {
int n = isConnected.length;
int[] parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (isConnected[i][j] == 1) {
union(parent, i, j);
}
}
}
Set<Integer> set = new HashSet<>();
for (int i = 0; i < n; i++) {
set.add(find(parent, i));
}
return set.size();
}
private int find(int[] parent, int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}
private void union(int[] parent, int a, int b) {
int rootA = find(parent, a);
int rootB = find(parent, b);
if (rootA != rootB) {
parent[rootB] = rootA;
}
}
}
Complexity Analysis
Union-Find with path compression → near constant per operation.
Quick Revision (Brute Force)
- DFS each unvisited node
- Count connected components
- O(N^2)
Quick Revision (Optimal)
- Union-Find
- Group nodes
- Count unique parents