DSA interview question

Number of Provinces

Medium · Data structures · Topics: graph, dfs, bfs, union find

The problem

A country has n cities. Some are directly connected by roads, and cities connected directly or indirectly belong to the same province. The road network is given as an adjacency matrix: isConnected[i][j] = 1 if cities i and j are directly connected. How many provinces are there? That's the number of connected components. Start a DFS from every city not yet visited and count how many times you had to start one.

Example: [[1,1,0], [1,1,0], [0,0,1]] → 2.

Function signature

int findCircleNum(const vector<vector<int>>& isConnected);

Test cases

Input (adjacency matrix)	Output	Explanation
`[[1,1,0],[1,1,0],[0,0,1]]`	`2`	{0, 1} and {2}
`[[1,0,0],[0,1,0],[0,0,1]]`	`3`	No roads
`[[1,0,0,1],[0,1,1,0],[0,1,1,1],[1,0,1,1]]`	`1`	0-3-2-1 links everything
`[[1,1,1],[1,1,1],[1,1,1]]`	`1`
`[[1]]`	`1`

(Confirm: the matrix is symmetric with 1s on the diagonal; n ≤ 200.)

How interviewers phrase it

"Given an n x n matrix isConnected, return the total number of provinces" (LeetCode 547).

Clarifying questions to ask

Is the matrix symmetric? (Yes: roads are undirected.)
Does the diagonal matter? (It's always 1 and can be ignored.)
How large is n? (Up to 200, so O(n²) is fine.)

Follow-ups to expect

"Why is it O(n²)?"
"DSU approach?"
"Should you convert to an adjacency list first?"
"How do you count components in general?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview