Number of Provinces

There are n cities, some connected directly. You are given an n × n matrix isConnected where isConnected[i][j] == 1 means city i and city j are directly connected (the matrix is symmetric and the diagonal is 1). A province is a group of cities connected directly or indirectly. Return the total number of provinces.

Hints

· Stuck? Reveal one nudge at a time.

Treat each row of the matrix as a city's neighbour list.

A province is a connected component — flood each unvisited city.

Union-Find alternative: union every pair (i, j) with isConnected[i][j] == 1.

Common doubts

The graph is given as an n×n matrix, so just reading it — finding each city's neighbours — costs n² regardless of the algorithm.

Yes — it's the same problem; you just derive neighbours by scanning matrix rows instead of a stored list.

The matrix is symmetric, so the lower triangle repeats the upper; scanning half avoids redundant unions.

Interview follow-ups

· What an interviewer asks next.

Store it as an adjacency list instead, dropping the cost from O(n²) to O(n + edges).

Track component sizes during the flood or with a size array in union-find.

Fun facts

This is LeetCode 547 — the matrix-flavoured twin of counting connected components.
The 'friend circles' framing is the same problem with people instead of cities.

Asked at

AmazonMicrosoftAdobe

Frequently Sometimes Occasionally

Example 1

Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output: 2
Cities 0 and 1 form one province; city 2 is another.

Example 2

Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3
No connections, so three provinces.

Constraints

- 1 <= n <= 200 - isConnected[i][j] is 0 or 1 - isConnected[i][i] == 1 - isConnected[i][j] == isConnected[j][i]

A province is a connected component — the twist is the graph arrives as an adjacency matrix rather than an edge list. Two standard counts:

DFS/BFS flood. From each unvisited city, walk to every directly-connected city (scan row isConnected[u]), marking the whole province; each fresh start is a new province. Scanning rows makes it O(n²), which is optimal given an n × n matrix.

Union-Find. Union i and j whenever isConnected[i][j] == 1 (only the upper triangle needs checking, since it's symmetric). Start the count at n and subtract one per real merge. Also O(n²) to scan the matrix, with near-constant union cost.

Prerequisites

Before you start

· Concepts used directly in the solution.

Matrix as graph. isConnected[u] is u's adjacency row.

Components. a province = one connected component.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“Is the matrix symmetric?”

Yes, and the diagonal is 1 (each city connects to itself).

“Direct vs indirect connection?”

Indirect still merges them into one province.

The ideal opening — say it like this

Each row of the matrix is a city's neighbour list, so I flood each unvisited city — one flood per province.

Or union-find: union every connected pair and count how many merges happen. Both are O(n²) to read the matrix.

Understand the problem

Worked example — isConnected = [[1,1,0],[1,1,0],[0,0,1]]

flood 0 -> reaches 1 (isConnected[0][1]=1) -> province {0,1}
flood 2 -> isolated             -> province {2}
answer = 2

Key observations

1Aha

Rows are adjacency lists

Neighbours of u are the columns v with isConnected[u][v] == 1.

2Aha

Symmetry halves the work

Only the upper triangle (j > i) needs checking for union-find.

3Aha

O(n²) is optimal here

Reading an n×n matrix already costs n².

Brute force vs optimal

	DFS flood	Union-Find
Idea	Flood each unvisited city via its row	Union connected pairs, count merges
Time	O(n²)	O(n² α)
Space	O(n)	O(n)

Both count provinces in O(n²), dominated by reading the matrix. Full code is in the Approaches selector below.

Summary

Key takeaway

A province is a connected component of the matrix graph. Flood each unvisited city (scanning its row), or union every connected pair and count merges. O(n²) time.

for each city: if unvisited: provinces++, dfs(city)   # neighbours = row 1s