547. Number of Provinces - Detailed Explanation

Problem statement

There are n cities numbered from 0 to n-1. You are given an n × n isConnected matrix where isConnected[i][j] = 1 if the ith and jth cities are directly connected, and isConnected[i][j] = 0 otherwise. A province is a group of directly or indirectly connected cities (an undirected connected component). Return the total number of provinces.

Examples

Example 1

Input  
isConnected = [
  [1,1,0],
  [1,1,0],
  [0,0,1]
]
Output  
2

Explanation
Cities 0 and 1 are connected, forming one province; city 2 is isolated, forming a second.

Example 2

Input  
isConnected = [
  [1,0,0],
  [0,1,0],
  [0,0,1]
]
Output  
3

Explanation
No two distinct cities are connected, so each forms its own province.

Constraints

• 1 ≤ n = isConnected.length = isConnected[i].length ≤ 200
• isConnected[i][i] = 1 for all i
• isConnected[i][j] = isConnected[j][i] ∈ {0,1}

Which pattern this problem belongs to

This question is an instance of the Graphs pattern. The cities are vertices, the matrix entries are edges, and each province is one connected component. Counting components is among the graph tasks interviewers reuse most, so the template is worth memorizing.

Design Gurus teaches this exact problem in the Number of Provinces lesson of Grokking the Coding Interview, beside the other graph traversals. Our guide to recurring LeetCode patterns records how often component counting returns under a fresh story.

Intuition

The task reduces to counting connected components in an undirected graph that arrives as an adjacency matrix. Two techniques solve it:

• DFS or BFS from each unvisited city. Mark every reachable city as visited and increment your province count.
• Union-Find, also called Disjoint Set Union. Union every pair of directly connected cities, then count the distinct roots.

Depth-first search (DFS) follows one path as deep as it goes before it backtracks and tries another. Union-Find instead stores each component as a tree, so it can report which component any city currently belongs to.

Depth-first search approach

Explanation

1. Maintain a visited array of size n.
2. For each city i from 0 to n-1, check whether it is visited. If it is not, start a DFS that marks every city reachable from i.
3. Each finished DFS has discovered one province, so increment count.

Algorithm

count = 0
visited = [false] * n
for i in 0…n-1:
  if not visited[i]:
    dfs(i)
    count += 1

function dfs(u):
  visited[u] = true
  for v in 0…n-1:
    if isConnected[u][v] == 1 and not visited[v]:
      dfs(v)

Step-by-step walkthrough

isConnected = [
  [1,1,0],
  [1,1,0],
  [0,0,1]
]

• i=0 is not visited, so dfs(0) marks city 0. It then sees that v=1 is connected, so dfs(1) marks city 1. The traversal returns and count becomes 1.
• i=1 is already visited, so skip it.
• i=2 is not visited, so dfs(2) marks city 2 and count becomes 2.

The function returns 2.

Union-Find approach

Explanation

1. Initialize parent[i]=i for all i, and count = n, since each city starts as its own province.
2. For every pair (i,j) with isConnected[i][j]==1, call union(i,j). If the two cities had different roots, decrement count.
3. At the end, count equals the number of provinces.

Algorithm

parent[i] = i for i in 0…n-1
count = n

function find(x):
  while parent[x] != x:
    parent[x] = parent[parent[x]]
    x = parent[x]
  return x

function union(a,b):
  ra = find(a), rb = find(b)
  if ra != rb:
    parent[rb] = ra
    count -= 1

for i in 0…n-1:
  for j in i+1…n-1:
    if isConnected[i][j] == 1:
      union(i, j)

return count

The find function here rewrites parent[x] as it climbs, which is path compression. Compression flattens the trees, so later queries reach a root in almost constant time.

Complexity analysis

• Time
  • DFS/BFS: O(n²) in worst case, since each node costs one adjacency-matrix scan
  • Union-Find: O(n² · α(n)) ≈ O(n²)
• Space
  • O(n²) for input, O(n) extra for visited or parent arrays