Skip to main content
Talentd

Number of Provinces - Solution & Explanation

MediumDepth-First SearchBreadth-First SearchUnion FindGraph25 min readAsked at: Amazon, Microsoft, Meta +6
Practice this problem

Problem Statement

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.

A province is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of provinces.

 

Example 1:

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

Example 2:

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

 

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]

Approach Overview

Problem Overview: You are given an n x n adjacency matrix isConnected where isConnected[i][j] = 1 means city i and city j are directly connected. A province is a group of cities connected directly or indirectly. The task is to count how many such provinces exist.

Approach 1: Depth-First Search (DFS) (Time: O(n2), Space: O(n))

Treat the matrix as a graph where each city is a node and isConnected[i][j] = 1 represents an undirected edge. Iterate through every city. When you encounter a city that hasn’t been visited, start a DFS traversal and mark all reachable cities as visited. That traversal covers exactly one connected component, which corresponds to a province. Since the adjacency matrix requires scanning all n neighbors for each node, the traversal costs O(n2). This approach directly applies classic Depth-First Search on a graph and is usually the most intuitive way to reason about connected components.

Approach 2: Union-Find (Disjoint Set) (Time: O(n2 · α(n)), Space: O(n))

Union-Find models each city as part of a disjoint set. Initially every city is its own parent. Scan the adjacency matrix and whenever isConnected[i][j] = 1, perform a union operation to merge the sets containing i and j. Path compression and union-by-rank keep operations nearly constant time, giving an amortized O(α(n)) cost per union. After processing the matrix, the number of unique roots represents the number of provinces. This approach works well when you repeatedly merge components or when connectivity queries appear in larger systems using Union Find.

Recommended for interviews: DFS (or BFS) is the most expected explanation because the problem maps directly to counting connected components in a graph. Interviewers want to see that you recognize the adjacency matrix as a graph representation and run a traversal to mark visited nodes. Union-Find is equally valid and demonstrates deeper familiarity with graph connectivity techniques. Start with DFS to show clear reasoning, then mention Union-Find as an alternative optimization pattern.

Approach 1: Approach 1: Depth-First Search (DFS)

This approach uses Depth-First Search (DFS) to count the number of provinces. The core idea is to treat the connected cities as a graph and perform a DFS traversal starting from each city. During traversal, mark all reachable cities from the starting city. Each starting city for a DFS that visits new cities indicates the discovery of a new province.

The objective is to find connected components in the graph, which represent provinces. We declare a boolean array visited to track visited cities. We implement a helper function dfs to perform DFS traversal from each unvisited node, marking all reachable nodes. Each DFS starting from an unvisited node suggests a new province has been found.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2), as we may visit each cell in the matrix.
Space Complexity: O(n) for the visited array.

Try this approach in the editor →

Approach 2: Approach 2: Union-Find

This approach employs the Union-Find (Disjoint Set Union) algorithm to find the number of provinces. This algorithm efficiently handles dynamic connectivity queries. By iteratively checking connections and performing unions, we can identify distinct connected components (provinces).

The Union-Find approach involves two primary operations: 'find' and 'union'. Each city starts as its own component, and each connection adds to the union. The find method returns the root ancestor for any node, which helps in determining connected components. The total provinces are the count of unique roots in the parent array.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2 * α(n)), where α is the inverse Ackermann function representing nearly constant time for union-find operations.
Space Complexity: O(n), the space for parent and rank arrays.

Try this approach in the editor →

Approach 3: DFS

We create an array vis to record whether each city has been visited.

Next, we traverse each city i. If the city has not been visited, we start a depth-first search from that city. Using the matrix isConnected, we find the cities directly connected to this city. These cities and the current city belong to the same province. We continue the depth-first search for these cities until all cities in the same province have been visited. This counts as one province, so we increment the answer ans by 1. Then, we move to the next unvisited city and repeat the process until all cities have been traversed.

Finally, return the answer.

The time complexity is O(n^2), and the space complexity is O(n). Here, n is the number of cities.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Approach 4: Union-Find

We can also use the union-find data structure to maintain each connected component. Initially, each city belongs to a different connected component, so the number of provinces is n.

Next, we traverse the matrix isConnected. If there is a connection between two cities (i, j) and they belong to two different connected components, they will be merged into one connected component, and the number of provinces is decremented by 1.

Finally, return the number of provinces.

The time complexity is O(n^2 times log n), and the space complexity is O(n). Here, n is the number of cities, and log n is the time complexity of path compression in the union-find data structure.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Depth-First Search (DFS)

Time Complexity: O(n^2), as we may visit each cell in the matrix.
Space Complexity: O(n) for the visited array.

Approach 2: Union-Find

Time Complexity: O(n^2 * α(n)), where α is the inverse Ackermann function representing nearly constant time for union-find operations.
Space Complexity: O(n), the space for parent and rank arrays.

DFS—
Union-Find—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Depth-First Search (DFS)O(n^2)O(n)Best general solution when treating the matrix as a graph and counting connected components.
Union-Find (Disjoint Set)O(n^2 · α(n))O(n)Useful when repeatedly merging components or solving dynamic connectivity problems.

Video Solution

G-7. Number of Provinces | C++ | Java | Connected Components • take U forward • 587,476 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Number of Provinces easy or hard?
Number of Provinces is categorized as a Medium problem on LeetCode. The core idea—counting connected components in a graph—is straightforward once you recognize the adjacency matrix representation, but it requires familiarity with DFS, BFS, or Union-Find.
How to solve Number of Provinces in O(n^2)?
Iterate through each city and run a DFS or BFS if it has not been visited. During traversal, mark all directly or indirectly connected cities as visited. Each traversal corresponds to one connected component, so increment the province count after each new traversal.
What is the best approach for Number of Provinces?
Depth-First Search is the most common approach. Treat each city as a node and run DFS whenever you encounter an unvisited city to mark all connected cities. Each DFS traversal represents one province. The overall time complexity is O(n^2) because the adjacency matrix requires scanning all neighbors.
What data structure is used in Number of Provinces?
The problem uses a graph represented as an adjacency matrix. Solutions typically rely on DFS or BFS traversal with a visited array, or the Union-Find (Disjoint Set) data structure to merge and track connected components.
What is the time complexity of Number of Provinces?
The standard DFS or BFS solution runs in O(n^2) time because the algorithm scans every entry of the n x n adjacency matrix. Union-Find also requires iterating through the matrix, resulting in O(n^2 · α(n)) time where α(n) is the inverse Ackermann function.
Number of Provinces Python or Java solution approach?
Both Python and Java implementations typically use DFS or Union-Find. The DFS version recursively visits neighbors using the adjacency matrix and tracks visited cities, achieving O(n^2) time and O(n) space complexity.
Is Number of Provinces asked at Google, Amazon, or Meta?
Number of Provinces is a common graph connectivity problem frequently asked in technical interviews. Variants of this problem have appeared at companies like Amazon, Google, Meta, and Microsoft because it tests understanding of graphs, traversal algorithms, and connected components.

Ready to solve this problem?

Practice Number of Provinces with our built-in code editor and test cases.

Practice on FleetCode
Previous

Detonate the Maximum Bombs

Next

Number of Connected Components in an Undirected Graph