Number of Provinces
Problem Statement
There are n cities. isConnected is an n × n table. Cell [i][j] is 1 when city i is directly connected to city j, and 0 when it is not. The table is symmetric, and each city is connected to itself.
A province is a group of cities that can reach each other through direct or indirect connections, and that has no connection to any city outside the group. Return how many provinces there are.
An n × n table isConnected of 1s and 0s.
The number of provinces (connected groups of cities).
Cities 0 and 1 are linked to each other, and city 2 stands alone. That makes two groups.
No two cities are linked, so every city is its own province.
- • 1 ≤ n ≤ 200
- • n = isConnected.length, and each row has n entries
- • isConnected[i][j] is 1 or 0
- • isConnected[i][i] = 1
- • isConnected[i][j] = isConnected[j][i]
Pattern Recognition Clues
Recognising these key signals in the problem description immediately identifies the pattern:
Approach Complexity Ladder
Each city keeps taking the smallest label among its neighbours; count the distinct labels at the end
Count the DFS starts: each unvisited city starts a new province and marks everything it can reach
Give each city its own number as a label. Repeat rounds: every city looks at the cities it is directly linked to and takes the smallest label it sees. Stop when a whole round changes nothing. Cities in the same province end with the same label, so the number of distinct labels is the number of provinces.
Recognition rule for this sub-pattern:
Unlock Complete Visual Walkthrough & Optimal C++
The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.
First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.
How this concept connects to System Design & C++ Systems
Top engineering interviews test whether you understand how algorithms like Graph BFS / DFS translate into production architectures and low-level memory mechanics.