MediumDepth-First SearchBreadth-First SearchUnion FindGraphUpdated Sep 2026

547. Number of Provinces

Asked at Uber

Difficulty

Medium

Time

O(n^2)

Space

O(n)

Pattern

Depth-First Search

Companies

1

Problem

You are given n cities and a square matrix isConnected of size n x n. The value isConnected[i][j] is 1 when city i and city j are directly connected, and 0 when they are not.

Connections spread. If a is connected to b, and b is connected to c, then a and c belong to the same group even though they have no direct link. A province is a group of cities that are all connected to each other, directly or indirectly, and that has no connection to any city outside the group.

Return the number of provinces. In graph words, this is the number of connected components of an undirected graph, where each city is a node and each 1 in the matrix is an edge.

Cities and their links

isConnected012012110110001A 1 at (i, j) means city i and city j are directlyconnected
Cities 0 and 1 are linked, so they share a province; city 2 stands alone, giving 2 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]

Examples

Example 1
InputisConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output2
WhyCity 0 and city 1 are joined, so they form one province. City 2 is linked to nobody, so it forms a province by itself. That gives 2 provinces.
Example 2
InputisConnected = [[1,0,0],[0,1,0],[0,0,1]]
Output3
WhyNo city is connected to any other city, so every city is its own province. The answer is 3.

Asked At

1 companies
CompanyDifficulty
UberMediumView all Uber questions →

How to Think About It

1

Model the problem as an undirected graph where matrix[i][j]=1 means an edge exists

2

Use DFS or BFS to traverse all nodes reachable from each unvisited starting node

3

Each unvisited node starts a new province, increment counter and explore all reachable nodes

4

Union-Find can solve this with path compression and union by rank

5

The answer equals the number of connected components in the graph

Optimal Approach

Treat the adjacency matrix as an undirected graph. Iterate through each city. If it has not been visited, start a DFS/BFS from it to mark all connected cities as visited, and increment the province count. The DFS explores all neighbors (where matrix[i][j]==1) recursively. Union-Find is an alternative: initialize each city as its own parent, then union cities that have an edge. The number of distinct roots equals the number of provinces.

Flood fill from each unvisited city

isConnected012012110110001Start at city 0, mark it, then follow its 1s to city 1— province count becomes 1isConnected012012110110001City 2 is still unvisited, so it starts a new province— count becomes 2for each city: if not visited: provinces += 1; dfs(city)dfs marks the city and all cities reachable from it
Each time we meet a city we have never seen, that city starts a new province and we mark everything reachable from it.
ComplexityTime O(n^2)Space O(n)Every city is visited once, and for each city we scan its whole row of n entries; the visited set and recursion stack hold at most n items.

What Trips People Up in Real Interviews

1

Clarify the matrix is symmetric since the graph is undirected

2

Confirm the diagonal is always 1 (each city connects to itself)

3

Mention DFS, BFS, and Union-Find all work with similar time complexity

4

Discuss that Union-Find is preferred when edges arrive as a stream

5

Note that the matrix representation is O(n²) space regardless of edge count

Solution Code

O(n^2) time
class Solution:
    def findCircleNum(self, isConnected: list[list[int]]) -> int:
        n = len(isConnected)
        visited = set()

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

        provinces = 0
        for city in range(n):
            if city not in visited:
                dfs(city)
                provinces += 1

        return provinces

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Number of Provinces problem?

Given an adjacency matrix representing connections between cities, find the number of connected components (provinces). Two cities are directly connected if the matrix value is 1, and transitively connected through other cities. This is the classic connected components problem in graph theory.

How do you solve Number of Provinces?

The optimal approach runs in O(n^2) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Number of Provinces?

Number of Provinces is asked at Uber. It is a medium difficulty problem.

What are common mistakes on Number of Provinces?
  • Clarify the matrix is symmetric since the graph is undirected
  • Confirm the diagonal is always 1 (each city connects to itself)
  • Mention DFS, BFS, and Union-Find all work with similar time complexity
  • Discuss that Union-Find is preferred when edges arrive as a stream
  • Note that the matrix representation is O(n²) space regardless of edge count