Number of Provinces

Number of Provinces

What is this problem about?

The Number of Provinces problem gives you an adjacency matrix where isConnected[i][j] = 1 means city i and city j are directly connected. A province is a group of directly or indirectly connected cities. Count the total number of provinces. This Number of Provinces coding problem is equivalent to counting connected components in an undirected graph.

Why is this asked in interviews?

Uber, Microsoft, Meta, Amazon, Google, Bloomberg, and Adobe ask this because it's a fundamental graph connectivity problem presented in adjacency matrix form. It tests whether candidates can work with both adjacency lists and matrices, and apply DFS, BFS, or Union-Find for component counting. The union find, BFS, graph, and DFS interview pattern is directly demonstrated.

Algorithmic pattern used

DFS from each unvisited node. Mark each city as visited when first reached. Start a DFS from each unvisited city, marking all reachable cities. Each DFS invocation = one province. Count total invocations.

Union-Find alternative: For each pair where isConnected[i][j]=1, union cities i and j. Count final components.

Example explanation

isConnected:

[[1,1,0],
 [1,1,0],
 [0,0,1]]

• DFS from 0: visits 0, then 1 (isConnected[0][1]=1). Province 1.
• DFS from 2: visits 2 only. Province 2. Total provinces = 2.

Common mistakes candidates make

• Treating the diagonal (isConnected[i][i]=1) as an edge (it's reflexive, not a connection).
• Iterating the full n×n matrix per DFS step (use the row as adjacency list: isConnected[node]).
• Not marking visited before recursing (revisit cycles for undirected graph).
• Confusing this with directed graph (connections are symmetric here).

Interview preparation tip

Number of Provinces is structurally identical to Number of Islands but on an adjacency matrix instead of a grid. Recognizing this equivalence is key: both count connected components in an undirected graph. Practice converting between adjacency matrix and adjacency list representations — both appear in interviews. Dijkstra, DFS, BFS, and Union-Find all work equivalently for connected component counting.