Number of Provinces
Number of Provinces is a medium graphs problem solved with the connected components pattern.
The best approach, union-find (disjoint set), runs in O(n² · α(n)) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from dfs / bfs counting components up.
Problem
There are n cities. isConnected[i][j] = 1 means city i and city j are directly connected. A province is a group of cities connected directly or indirectly. Return the number of provinces.
The sheet’s note: count connected components with DFS first, then with BFS.
Examples
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 <= 200; the matrix is symmetric with 1s on the diagonal.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 9 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| DFS / BFS counting components | O(n²) | O(n) |
| Union-Find (disjoint set) | O(n² · α(n)) | O(n) |
1DFS / BFS counting components
O(n²)The adjacency matrix has n² entries.O(n)Loop over cities. When a city is unvisited, start a DFS that marks every city reachable from it and count one province.
- For each i: if not seen, count++ and dfs(i).
- dfs(u): mark; for each v with isConnected[u][v] == 1 and not seen, dfs(v).
class Solution {
public int findCircleNum(int[][] isConnected) {
int n = isConnected.length, count = 0;
boolean[] seen = new boolean[n];
for (int i = 0; i < n; i++) {
if (seen[i]) continue;
count++;
dfs(isConnected, i, seen);
}
return count;
}
private void dfs(int[][] g, int u, boolean[] seen) {
seen[u] = true;
for (int v = 0; v < g.length; v++) if (g[u][v] == 1 && !seen[v]) dfs(g, v, seen);
}
}class Solution:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
n, count = len(isConnected), 0
seen = [False] * n
for i in range(n):
if seen[i]:
continue
count += 1
self.dfs(isConnected, i, seen)
return count
def dfs(self, g: List[List[int]], u: int, seen: List[bool]) -> None:
seen[u] = True
for v in range(len(g)):
if g[u][v] == 1 and not seen[v]:
self.dfs(g, v, seen)class Solution {
public:
int findCircleNum(vector<vector<int>>& isConnected) {
int n = isConnected.size(), count = 0;
vector<bool> seen(n, false);
for (int i = 0; i < n; i++) {
if (seen[i]) continue;
count++;
dfs(isConnected, i, seen);
}
return count;
}
private:
void dfs(vector<vector<int>>& g, int u, vector<bool>& seen) {
seen[u] = true;
for (int v = 0; v < (int)g.size(); v++) if (g[u][v] == 1 && !seen[v]) dfs(g, v, seen);
}
};function findCircleNum(isConnected) {
const n = isConnected.length;
let count = 0;
const seen = new Array(n).fill(false);
for (let i = 0; i < n; i++) {
if (seen[i]) continue;
count++;
dfs(isConnected, i, seen);
}
return count;
}
function dfs(g, u, seen) {
seen[u] = true;
for (let v = 0; v < g.length; v++) if (g[u][v] === 1 && !seen[v]) dfs(g, v, seen);
}2Union-Find (disjoint set)
O(n² · α(n))α is the inverse Ackermann function, effectively constant.O(n)Start with n separate sets. Union the two cities of every connection; each successful union removes one set. The number of sets left is the number of provinces.
- parent[i] = i; count = n.
- For each i < j with a connection: if find(i) != find(j), union them and count--.
class Solution {
private int[] parent;
public int findCircleNum(int[][] isConnected) {
int n = isConnected.length, count = n;
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) {
int a = find(i), b = find(j);
if (a != b) { parent[a] = b; count--; }
}
return count;
}
private int find(int x) {
while (parent[x] != x) x = parent[x] = parent[parent[x]];
return x;
}
}class Solution:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
n = count = len(isConnected)
self.parent = list(range(n))
for i in range(n):
for j in range(i + 1, n):
if isConnected[i][j] == 1:
a, b = self.find(i), self.find(j)
if a != b:
self.parent[a] = b
count -= 1
return count
def find(self, x: int) -> int:
parent = self.parent
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return xclass Solution {
vector<int> parent;
public:
int findCircleNum(vector<vector<int>>& isConnected) {
int n = isConnected.size(), count = n;
parent.assign(n, 0);
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) {
int a = find(i), b = find(j);
if (a != b) { parent[a] = b; count--; }
}
return count;
}
private:
int find(int x) {
while (parent[x] != x) x = parent[x] = parent[parent[x]];
return x;
}
};function findCircleNum(isConnected) {
const n = isConnected.length;
let count = n;
const parent = new Array(n);
for (let i = 0; i < n; i++) parent[i] = i;
function find(x) {
while (parent[x] !== x) x = parent[x] = parent[parent[x]];
return x;
}
for (let i = 0; i < n; i++)
for (let j = i + 1; j < n; j++)
if (isConnected[i][j] === 1) {
const a = find(i), b = find(j);
if (a !== b) { parent[a] = b; count--; }
}
return count;
}Edge cases to test
- Every city isolated
- Everything connected
Hints
Hint 1
Each DFS started from an unvisited city marks one whole province.
FAQ
What is the best time complexity for Number of Provinces?
Union-Find (disjoint set) runs in O(n² · α(n)) time and O(n) extra space. α is the inverse Ackermann function, effectively constant.
Which pattern does Number of Provinces use?
It is a graphs problem that uses the connected components pattern. Other problems with the same pattern: Number of Islands, Evaluate Division, Making A Large Island.
Is there a brute force solution for Number of Provinces?
Yes. DFS / BFS counting components takes O(n²) time and O(n) space. Loop over cities.
Which edge cases should I test for Number of Provinces?
Every city isolated; Everything connected.