Number of Provinces

Problem

There are n cities. Some of them are connected. A province is a group of directly or indirectly connected cities. Given an n x n matrix isConnected, return the total number of provinces.

Examples

The brute-force approach

DFS or BFS from each unvisited city, marking all reachable cities as visited. Count how many times you start a new traversal.

visited = [False] * n
count = 0
def dfs(city):
    for neighbor in range(n):
        if isConnected[city][neighbor] == 1 and not visited[neighbor]:
            visited[neighbor] = True
            dfs(neighbor)
for i in range(n):
    if not visited[i]:
        visited[i] = True
        dfs(i)
        count += 1
return count

O(n²) — must inspect every cell of the adjacency matrix. This is already the standard approach.

Spotting the pattern

This is a Graph Traversal problem. The key question to ask yourself:

This problem is equivalent to counting connected components in a graph. How does DFS/BFS help you identify one connected component at a time?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.