547. Number of Provinces

Number of Provinces (LeetCode 547) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Graph DFS - Connected Components / Island Counting subpattern.

How to solve Number of Provinces

Number of Provinces is a DFS Connected Components problem, part of Graph Traversal Patterns (DFS & BFS). Use DFS to find connected components and count islands in grids. Flood fill and province counting problems.

Work towards the solution in these steps:

1. Consider modeling the cities and their direct connections as a graph where nodes represent cities and edges represent connections.
2. Think about how to identify groups of directly or indirectly connected cities; what graph traversal methods can help you explore connected components?
3. Implement a traversal method such as DFS or BFS starting from an unvisited city to mark all cities in the same province as visited.

The reference solution runs in O(n^2) time and O(n) space.

The Number of Provinces solution and editorial walks through the full approach with reference code.

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]

Topics and companies

Topics: Depth-First Search, Breadth-First Search, Union Find, Graph.

Reported in interviews at Amazon, Two Sigma, Goldman Sachs, Dropbox, Facebook, Audible.

How to practise Number of Provinces on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n^2) time and O(n) space.

Open Number of Provinces in the code editor, or read the Number of Provinces editorial for a worked solution with its approach and complexity analysis.

Where Number of Provinces sits in the DSA pattern sheet

• Graph Traversal Patterns (DFS & BFS) pattern guide
• Graph DFS - Connected Components / Island Counting subpattern
• The full DSA patterns sheet

Problems related to Number of Provinces

Other problems that use the same Graph DFS - Connected Components / Island Counting and Graph Traversal Patterns (DFS & BFS) techniques:

• Count Sub Islands — Medium, same subpattern
• Detonate the Maximum Bombs — Medium, same subpattern
• Evaluate Division — Medium, same subpattern
• Flood Fill — Easy, same subpattern
• Island Perimeter — Easy, same subpattern
• Keys and Rooms — Medium, same subpattern

Number of Provinces FAQ