Problem Statement

Number of Provinces

There are n cities. Some cities are connected to each other, and some are not. Connection passes along: if city a is directly connected to city b, and city b is directly connected to city c, then a and c count as connected too, even with no direct link between them. A province is a group of cities that are all connected, directly or indirectly, with no other city left out of the group. You are given an n x n grid called isConnected, where isConnected[i][j] = 1 means city i and city j are directly connected, and 0 means they are not. Your job is to return how many provinces there are. In plain terms, you are counting the separate clusters of connected cities.

mediumUnion FindGraphUnion FindTime: O(n^2 * α(n)) · Space: O(n)

Signals to notice

count friend groupsadjacency matrixconnected components

Brute force first

DFS/BFS from each unvisited node. Traverses the adjacency matrix. That direct path helps you understand the question, but it tends to treat every possibility as brand new instead of learning from earlier steps.

The key insight

Union-Find: for each pair (i,j) where isConnected[i][j] = 1, union(i,j). Count distinct roots. — still for reading the matrix, but Union-Find is cleaner for connectivity. Instead of recomputing the world every time, you preserve just enough context to let the next decision become obvious.

Trace it on `isConnected=[[1,1,0],[1,1,1],[0,1,1]]`

init: parent=[0,1,2], rank=[0,0,0]
(0,1): isConnected[0][1]=1 -> union(0,1); roots 0,1 equal rank -> parent[1]=0, rank=[1,0,0]; parent=[0,0,2]
(0,2): isConnected[0][2]=0 -> skip; parent=[0,0,2]
(1,2): isConnected[1][2]=1 -> union(1,2); find(1)=0, find(2)=2; rank[0]=1>rank[2]=0 -> parent[2]=0; parent=[0,0,0]
count roots: find(0)=0, find(1)=0, find(2)=0 -> {0}
return 1

What must stay true

Each connected component = one province. If i and j are connected (directly or transitively), they're in the same province. Union-Find tracks this transitivity automatically. As long as that statement keeps holding, you can trust the steps built on top of it.

Shape of the loop

parent = [0..n-1]; rank = [0]*n
for i in 0..n-1:
  for j in i+1..n-1:
    if isConnected[i][j] == 1: union(i, j)   // merge roots by rank
return count of distinct find(i) for all i

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Only checking direct connections — friend-of-friend is the same province. Union-Find handles transitivity; BFS/DFS does too via traversal. When the code becomes mechanical before the idea is clear, small edge cases start breaking the whole story.

Union Find Pattern