Number of Provinces Solution

Problem

You have n cities. A province is a group of cities where you can travel between any two cities directly or through other cities in the same province. You're given an n × n matrix where a 1 at position [i][j] means city i and city j are directly connected. Return the total number of provinces.

Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output: 2
Explanation: Cities 0 and 1 are connected and form one province; city 2 is isolated and forms another.

Counter-example: [[1,0,0],[0,1,0],[0,0,1]] → 3 (all three cities are isolated, so every city is its own province).

Intuition

This is a classic "count connected components" problem. Each province is a connected component in an undirected graph where cities are nodes and a 1 in the matrix means there's an edge. Counting components is equivalent to counting how many times you can start a fresh traversal from an unvisited node — each fresh start reveals exactly one province.

Approach 1 — DFS

Scan each city; whenever you find one you haven't visited, run a DFS that marks every reachable city in the same province, then increment the province counter.

Create a visited boolean array of size n.
Initialize province_count = 0.
For each city i from 0 to n-1: if not yet visited, start a DFS from i and increment province_count.
In the DFS: mark the current city visited, then for each potential neighbor j, if isConnected[city][j] == 1 and j is unvisited, recurse on j.
Return province_count.

1def findCircleNum(self, isConnected: list[list[int]]) -> int:
2    num_cities = len(isConnected)
3    visited = set()
4    province_count = 0
5
6    def dfs(city):
7        for neighbor in range(num_cities):
8            if isConnected[city][neighbor] == 1 and neighbor not in visited:
9                visited.add(neighbor)
10                dfs(neighbor)
11
12    for city in range(num_cities):
13        if city not in visited:
14            visited.add(city)
15            dfs(city)
16            province_count += 1
17
18    return province_count

Time: O(n²) — every cell in the matrix is visited exactly once across all DFS calls.

Space: O(n) — the visited array uses O(n), and the recursion stack depth is at most O(n) in a fully connected graph.

Approach 2 — Union-Find

Treat each city as a node in a disjoint-set structure. Merge cities that are directly connected, then count how many distinct root nodes remain — each root represents one province.

Initialize parent[i] = i so every city starts as its own component.
For each pair (i, j) with i < j: if isConnected[i][j] == 1, union their components.
Count cities where find(city) == city (cities that are their own root).
Return that count.

1def findCircleNum(self, isConnected: list[list[int]]) -> int:
2    num_cities = len(isConnected)
3    parent = list(range(num_cities))  # each city starts as its own root
4
5    def find(city):
6        if parent[city] != city:
7            parent[city] = find(parent[city])  # path compression flattens the tree
8        return parent[city]
9
10    def union(city_a, city_b):
11        root_a, root_b = find(city_a), find(city_b)
12        if root_a != root_b:
13            parent[root_a] = root_b  # attach one component's root to the other
14
15    for i in range(num_cities):
16        for j in range(i + 1, num_cities):  # upper triangle only; matrix is symmetric
17            if isConnected[i][j] == 1:
18                union(i, j)
19
20    return sum(1 for city in range(num_cities) if find(city) == city)

Time: O(n² · α(n)) ≈ O(n²) — we scan all n² pairs, and each union/find is effectively constant with path compression.

Space: O(n) — the parent array holds one entry per city.

Complexity Summary

Approach	Time	Space	When to use
DFS	O(n²)	O(n)	Default choice — simple, readable, no extra setup
Union-Find	O(n²)	O(n)	When edges arrive in a stream and you need to merge components incrementally without re-traversing

Common Mistakes

Confusing provinces with connections — it's easy to count edges (1s in the matrix) instead of connected components; every fresh DFS/UF start is one province, not every edge.
Using a visited array of wrong size — the array needs n entries (one per city), not n × n; the matrix dimensions can mislead.
Scanning the full matrix in Union-Find instead of the upper triangle — isConnected[i][j] == isConnected[j][i], so scanning j > i is sufficient and avoids redundant unions.
Forgetting path compression in Union-Find — without it, find() degrades to O(n) per call and the overall solution becomes O(n³).
Including the diagonal in DFS neighbor checks — isConnected[i][i] is always 1 (a city is connected to itself), but since the city is already marked visited before recursing, it causes no bug; still, iterating j = 0 to n-1 and filtering by j != city can make intent clearer for readers.

Number of Provinces — Solution