Number of Provinces - LeetCode75 Python Solution Explained

The Number of Provinces problem (LeetCode75) is a classic graph problem that tests your understanding of DFS/BFS, adjacency matrices and connected components. It is commonly asked in technical interviews because it evaluates problem-solving skills in graph traversal and connectivity analysis.

In this blog, we will break down the problem, provide examples, explain the Python solution step by step, analyze time and space complexity, discuss edge cases and explore real-world applications.

Problem Statement

You are given an n x n matrix isConnected where:

isConnected[i][j] = 1 if the i-th city is directly connected to the j-th city.
isConnected[i][j] = 0 otherwise.

A province is a group of directly or indirectly connected cities.

Return the number of provinces.

Example 1

Input:

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

Output:

Explanation:

Cities 0 and 1 are connected → 1 province
City 2 is isolated → 1 province

Example 2

Input:

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

Output:

Explanation:

All cities are isolated → 3 provinces

Complete Python Solution

from typing import List

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        def dfs(node):
            visited[node] = True
            for neighbor in range(n):
                if isConnected[node][neighbor] == 1 and not visited[neighbor]:
                    dfs(neighbor)

        n = len(isConnected)
        provinces = 0
        visited = [False] * n

        for i in range(n):
            if not visited[i]:
                provinces += 1
                dfs(i)

        return provinces

Step-by-Step Explanation

Step 1: Initialize Variables

visited array to track which cities have been visited.
provinces counter to track number of connected components.

n = len(isConnected)
visited = [False] * n
provinces = 0

Step 2: Define DFS Function

Use DFS to explore all cities connected to a given city:

def dfs(node):
    visited[node] = True
    for neighbor in range(n):
        if isConnected[node][neighbor] == 1 and not visited[neighbor]:
            dfs(neighbor)

Mark the current city as visited.
Recursively visit all connected cities.

Step 3: Traverse All Cities

Loop through all cities. If a city is not visited, it represents a new province.

for i in range(n):
    if not visited[i]:
        provinces += 1
        dfs(i)

Increment provinces for each new connected component.
Perform DFS to mark all cities in that province as visited.

Step 4: Return Number of Provinces

return provinces

Time and Space Complexity

Time Complexity:O(N^2)
- Looping through all N cities and checking connections using the adjacency matrix.
Space Complexity:O(N)
- Recursion stack depth in DFS and visited array of size N.

Edge Cases

Single city: isConnected = [[1]] → 1 province.
All cities connected: returns 1 province.
All cities disconnected: returns N provinces.

Real-World Applications

Social Networks: Counting connected groups of users.
Network Connectivity: Identifying isolated subnetworks.
City Infrastructure Planning: Determining clusters of connected cities.
Epidemiology: Tracking regions with interconnected populations for disease spread.

Conclusion

The Number of Provinces problem is an excellent exercise in DFS traversal, adjacency matrix analysis, and connected components detection. By exploring each city and marking all reachable cities, we can efficiently determine the number of connected clusters.

This problem enhances your understanding of:

Recursive DFS traversal
Adjacency matrix usage
Connected components in graphs

It is highly valuable for technical interviews and practical applications in networking, city planning and social network analysis.

Number of Provinces – LeetCode75 Python Solution Explained