Log inSign up
mediumLeetCodeNot Started

Number of Provinces

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. 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 th

Graph
Solve on LeetCode
Lesson

Problem Statement

### 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 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.

---

### Examples

Example 1: ``text Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]] Output: 2 Explanation: City 0 and City 1 are connected, forming Province 1. City 2 is isolated, forming Province 2. Total provinces = 2.

Example 2: ``text Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]] Output: 3 Explanation: All 3 cities are completely isolated, forming 3 separate provinces.

---

### Constraints - 1 <= n <= 200 - n == isConnected.length - n == isConnected[i].length - isConnected[i][j] is 1 or 0. - isConnected[i][i] == 1 - isConnected[i][j] == isConnected[j][i]

Constraints:

  • 1 <= n <= 200
  • isConnected[i][j] is 1 or 0
  • isConnected[i][i] == 1
  • isConnected[i][j] == isConnected[j][i]

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Identify connected component counting on adjacency matrices.
  • Contrast DFS, BFS, and DSU implementations on dense matrix representations.
  • Understand the tight O(n2) lower bound imposed by matrix edge representation.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Graph given as an n x n adjacency matrix
  • Counting distinct groups/clusters of directly or indirectly connected entities
  • Friend circles or transitive connectivity

Algorithmic Decision Tree:

  • If adjacency matrix provided -> O(n2) time is required to inspect the edges.
  • Use boolean visited array of size n to track visited vertices.
  • Count how many times an unvisited vertex triggers a new traversal.

Connected Patterns:

Number of IslandsGraph Valid TreeRedundant Connection

1. BFS with Queue and Visited Array

Intuition

Queue-based breadth-first search marks all reachable cities level by level before returning to the outer loop.

Algorithm

  1. Initialize visited array of size n to false.
  2. Initialize provinces = 0.
  3. Loop i from 0 to n - 1:
  4. If !visited[i]:
  5. provinces++.
  6. Initialize queue q and push i, visited[i] = true.
  7. While queue is not empty:
  8. Pop u from q.
  9. For v from 0 to n - 1:
  10. If isConnected[u][v] == 1 and !visited[v]:
  11. visited[v] = true, push v into q.
  12. Return provinces.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4
5class Solution {
6public:
7 int findCircleNum(std::vector<std::vector<int>>& isConnected) {
8 int n = isConnected.size();
9 std::vector<bool> visited(n, false);
10 int provinces = 0;
11
12 for (int i = 0; i < n; ++i) {
13 if (!visited[i]) {
14 provinces++;
15 std::queue<int> q;
16 q.push(i);
17 visited[i] = true;
18
19 while (!q.empty()) {
20 int u = q.front();
21 q.pop();
22
23 for (int v = 0; v < n; ++v) {
24 if (isConnected[u][v] == 1 && !visited[v]) {
25 visited[v] = true;
26 q.push(v);
27 }
28 }
29 }
30 }
31 }
32 return provinces;
33 }
34};
35
36int main() {
37 Solution sol;
38 std::vector<std::vector<int>> isConnected = {
39 {1, 1, 0},
40 {1, 1, 0},
41 {0, 0, 1}
42 };
43 std::cout << "BFS Provinces Count: " << sol.findCircleNum(isConnected) << " (Expected: 2)\n";
44 return 0;
45}

Time & Space Complexity

  • Time complexity: O(n^2)
  • Space complexity: O(n)

2. Recursive DFS Traversal

Intuition

When an unvisited city i is encountered, increment province count and recursively mark all connected cities via depth-first exploration along row i.

Algorithm

  1. Initialize visited array of size n to false.
  2. Initialize provinces = 0.
  3. Define dfs(u):
  4. visited[u] = true.
  5. For v from 0 to n - 1:
  6. If isConnected[u][v] == 1 and !visited[v]:
  7. dfs(v).
  8. Loop i from 0 to n - 1:
  9. If !visited[i]:
  10. provinces++.
  11. dfs(i).
  12. Return provinces.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5 void dfs(int u, const std::vector<std::vector<int>>& isConnected, std::vector<bool>& visited) {
6 visited[u] = true;
7 int n = isConnected.size();
8 for (int v = 0; v < n; ++v) {
9 if (isConnected[u][v] == 1 && !visited[v]) {
10 dfs(v, isConnected, visited);
11 }
12 }
13 }
14public:
15 int findCircleNum(std::vector<std::vector<int>>& isConnected) {
16 int n = isConnected.size();
17 std::vector<bool> visited(n, false);
18 int provinces = 0;
19
20 for (int i = 0; i < n; ++i) {
21 if (!visited[i]) {
22 provinces++;
23 dfs(i, isConnected, visited);
24 }
25 }
26 return provinces;
27 }
28};
29
30int main() {
31 Solution sol;
32 std::vector<std::vector<int>> isConnected = {
33 {1, 1, 0},
34 {1, 1, 0},
35 {0, 0, 1}
36 };
37 std::cout << "DFS Provinces Count: " << sol.findCircleNum(isConnected) << " (Expected: 2)\n";
38 return 0;
39}

Time & Space Complexity

  • Time complexity: O(n^2)
  • Space complexity: O(n)

3. Disjoint Set Union (DSU / Union-Find with Rank & Path Compression)

Intuition

Union-Find directly models transitive equivalence relationships. Initializing count = n and uniting connected endpoints provides optimal nearly-linear dynamic connectivity.

Algorithm

  1. Initialize DSU with n elements (parent[i] = i, rank[i] = 0) and componentCount = n.
  2. Loop i from 0 to n - 1:
  3. Loop j from i + 1 to n - 1 (upper triangle of symmetric matrix):
  4. If isConnected[i][j] == 1:
  5. If find(i) != find(j):
  6. unite(i, j).
  7. componentCount--.
  8. Return componentCount.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class DSU {
5 std::vector<int> parent, rank;
6 int count;
7public:
8 DSU(int n) : parent(n), rank(n, 0), count(n) {
9 for (int i = 0; i < n; ++i) parent[i] = i;
10 }
11 int find(int i) {
12 if (parent[i] == i) return i;
13 return parent[i] = find(parent[i]);
14 }
15 bool unite(int i, int j) {
16 int rootI = find(i);
17 int rootJ = find(j);
18 if (rootI != rootJ) {
19 if (rank[rootI] < rank[rootJ]) std::swap(rootI, rootJ);
20 parent[rootJ] = rootI;
21 if (rank[rootI] == rank[rootJ]) rank[rootI]++;
22 count--;
23 return true;
24 }
25 return false;
26 }
27 int getCount() const { return count; }
28};
29
30class Solution {
31public:
32 int findCircleNum(std::vector<std::vector<int>>& isConnected) {
33 int n = isConnected.size();
34 DSU dsu(n);
35
36 for (int i = 0; i < n; ++i) {
37 for (int j = i + 1; j < n; ++j) {
38 if (isConnected[i][j] == 1) {
39 dsu.unite(i, j);
40 }
41 }
42 }
43 return dsu.getCount();
44 }
45};
46
47int main() {
48 Solution sol;
49 std::vector<std::vector<int>> isConnected = {
50 {1, 1, 0},
51 {1, 1, 0},
52 {0, 0, 1}
53 };
54 std::cout << "DSU Provinces Count: " << sol.findCircleNum(isConnected) << " (Expected: 2)\n";
55 return 0;
56}

Time & Space Complexity

  • Time complexity: O(n^2 * alpha(n))
  • Space complexity: O(n)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.BFS with QueueO(n^2)O(n)FIFO queue explores each connected city cluster layer by layer.Matrix row scanning
2.Recursive DFS TraversalO(n^2)O(n)Recursively visits all neighbors along row u.Matrix row scanning
3.Disjoint Set Union (DSU / Union-Find)OptimalO(n^2 * alpha(n))O(n)Unions connected pairs over the upper triangle matrix.Upper triangle traversal

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Treating isConnected[i][j] as a 2D grid matrix rather than an adjacency matrix of n cities.

Pitfall 2:

Forgetting to check if isConnected[u][v] == 1 before visiting node v.

Pitfall 3:

Checking bounds for a grid rather than a 1D vertex index 0 to n - 1.

Crucial Edge Cases to Validate:

  • n = 1 (Single city) — Outer loop runs once, marks city 0 visited, returns 1.
  • Completely disconnected graph (identity matrix) — No cities share edges; outer loop increments counter n times, returning n.
  • Complete graph (all isConnected[i][j] = 1) — First traversal from city 0 visits all n cities, returning 1.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clarify immediately: 'The input is an adjacency matrix representation of n vertices, not a 2D map/grid like Number of Islands.'
  2. Mention that scanning only the upper triangle in DSU halves the number of matrix cell checks.
  3. Highlight that DSU is preferred if edges are arriving in a stream.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does any algorithm on this problem require at least O(n2) time?

2.Why can the DSU approach only scan the upper triangle of the matrix (j from i + 1 to n - 1)?

3.What is a province in this problem?

Back to DSA Sheet