DSA problem
Number of Provinces
You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the i-th and j-th cities are directly connected and isConnected[i][j] = 0 otherwise. A province is a group of directly or indirectly connected cities, with no city outside of the group. Return the total number of provinces.
The relation is symmetric and reflexive: isConnected[i][i] == 1 and isConnected[i][j] == isConnected[j][i]. The problem is asking for the number of connected components in an undirected graph whose adjacency matrix is given. Two approaches naturally fit: a DFS/BFS scan of the adjacency matrix, or a Disjoint Set Union (DSU) that unions every connected pair and then counts the unique roots.
The DSU approach is particularly clean here. We initialise each city as its own parent, then iterate over the upper triangle of the matrix (since the relation is symmetric) and call union(i, j) whenever isConnected[i][j] == 1. By the end of the loop, two cities share a root if and only if they belong to the same province, so the answer is simply the number of cities whose parent points to themselves.
With both path compression and union by rank, every find and union operation runs in nearly constant amortised time, giving an overall complexity of O(n^2 * alpha(n)) — practically O(n^2). The DSU pattern also generalises: it can be reused for any "merge equivalent classes" problem, which is why it is the canonical interview answer here.
Examples
isConnected = [[1,1,0],[1,1,0],[0,0,1]]2isConnected = [[1,0,0],[0,1,0],[0,0,1]]3isConnected = [[1,1,1],[1,1,1],[1,1,1]]1Constraints
- 1 <= n <= 200
- n == isConnected.length
- n == isConnected[i].length
- isConnected[i][j] is 1 or 0.
- isConnected[i][i] == 1 and isConnected[i][j] == isConnected[j][i].
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.