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.

Description Solution Video 15:29

547. Number of Provinces

Medium70.8% acceptance9 companies

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 i^th city and the j^th 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]

Asked at 9 companies

Two Sigma Adobe Amazon Bloomberg

Google Microsoft Meta Uber Pinterest

Topics

15:29

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution

547. Number of Provinces

Asked at 9 companies

Topics

Similar problems