Number of Provinces — InterviewPrepKit

Solving tips

A province is a connected component and isConnected is an adjacency matrix: neighbors of city i are the columns j where isConnected[i][j]==1.
Count fresh DFS/BFS starts over unvisited cities, or union every connected pair and count remaining sets; O(n^2) is forced because the dense matrix must be fully read.
In union-find iterate only j>i to skip the symmetric lower triangle and the all-1s diagonal (self-loops).
Pitfall: it's an adjacency matrix, not an edge list of literal [i,j] pairs, and only a successful merge should decrement the province count.

Problem

There are n cities. Some are directly connected, others aren’t. A province is a group of cities that are directly or indirectly connected, with no connections to cities outside the group.

You’re given an n x n matrix isConnected where isConnected[i][j] = 1 means city i and city j are directly connected, and 0 means they aren’t. The matrix is symmetric (isConnected[i][j] == isConnected[j][i]) and its diagonal is all 1s (a city is connected to itself).

Return the number of provinces.

Examples

isConnected = [[1,1,0],[1,1,0],[0,0,1]] → 2 — cities 0 and 1 are directly connected (one province), city 2 is alone (another).
isConnected = [[1,0,0],[0,1,0],[0,0,1]] → 3 — no city connects to any other, so three provinces.
isConnected = [[1,1,0],[1,1,1],[0,1,1]] → 1 — 0–1 and 1–2 are connected, so 0,1,2 form a single province via city 1.

Constraints

1 <= n <= 200
isConnected[i][j] is 0 or 1; the matrix is symmetric with isConnected[i][i] = 1.

Think about it first

Hint 1

A province is a connected component of the "cities" graph. The `isConnected` matrix is an adjacency matrix: row `i` tells you which cities `i` touches directly.

Hint 2

Walk over the cities. Each city you haven't visited begins a new province: DFS or BFS to mark every city reachable through direct/indirect connections, then move on. The number of traversals you start is the answer.

Hint 3

Union-find is a clean fit: for every pair `i < j` with `isConnected[i][j] == 1`, union `i` and `j`. Start the province count at `n` and decrement on each successful merge.

TL;DR

Count connected components over an adjacency matrix — DFS/BFS flood fill or union-find — O(n²) time (you must read every matrix cell), O(n) space.

Approach 1 — DFS over the adjacency matrix

This is connected-components counting; the direct solution is already efficient given the matrix input (any algorithm must read all n² entries at least once).

The insight: each unvisited city starts a new province; a DFS from it marks every city reachable via direct connections (and transitively their connections). Because the input is an adjacency matrix, city i’s neighbors are the columns j with isConnected[i][j] == 1.

class Solution:
    def findCircleNum(self, isConnected: list[list[int]]) -> int:
        n = len(isConnected)
        visited = [False] * n

        def dfs(city: int) -> None:
            visited[city] = True
            for nxt in range(n):
                if isConnected[city][nxt] == 1 and not visited[nxt]:
                    dfs(nxt)

        provinces = 0
        for city in range(n):
            if not visited[city]:
                provinces += 1
                dfs(city)
        return provinces

Walkthrough (isConnected = [[1,1,0],[1,1,1],[0,1,1]]): city 0 unvisited → provinces 1; DFS visits 0, then 1 (connected), then from 1 visits 2 (connected). All marked. Cities 1,2 already visited. Result 1.

Complexity: the DFS scans each city’s full row of n entries → O(n²) time, O(n) space (visited array + recursion). O(n²) is unavoidable because the graph is given as a dense matrix.

Approach 2 — BFS variant

The insight: same component count, iterative frontier. BFS is preferred when you want to avoid recursion depth (up to 200 here is safe either way, so this is mostly a style choice); DFS is preferred for its brevity.

from collections import deque

class Solution:
    def findCircleNum(self, isConnected: list[list[int]]) -> int:
        n = len(isConnected)
        visited = [False] * n
        provinces = 0
        for start in range(n):
            if visited[start]:
                continue
            provinces += 1
            queue = deque([start])
            visited[start] = True
            while queue:
                city = queue.popleft()
                for nxt in range(n):
                    if isConnected[city][nxt] == 1 and not visited[nxt]:
                        visited[nxt] = True
                        queue.append(nxt)
        return provinces

Complexity: O(n²) time, O(n) space.

Approach 3 — Union-Find (disjoint-set union)

The insight: provinces are equivalence classes under connectivity. Union every directly-connected pair (i, j); the number of distinct sets left is the province count. Union-find is the disjoint-set structure with near-constant find/union via path compression and union by rank. Because the matrix is symmetric, iterate only j > i.

class Solution:
    def findCircleNum(self, isConnected: list[list[int]]) -> int:
        n = len(isConnected)
        parent = list(range(n))
        rank = [1] * n
        provinces = n

        def find(x: int) -> int:
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        def union(a: int, b: int) -> None:
            nonlocal provinces
            ra, rb = find(a), find(b)
            if ra == rb:
                return
            if rank[ra] < rank[rb]:
                ra, rb = rb, ra
            parent[rb] = ra
            rank[ra] += rank[rb]
            provinces -= 1

        for i in range(n):
            for j in range(i + 1, n):
                if isConnected[i][j] == 1:
                    union(i, j)
        return provinces

Walkthrough (isConnected = [[1,1,0],[1,1,0],[0,0,1]]): start provinces 3. (0,1) connected → union → 2. (0,2),(1,2) are 0. Result 2.

Complexity: O(n²·α(n)) time (scanning the upper triangle dominates), O(n) space.

Common pitfalls

Reprocessing the diagonal / lower triangle. isConnected[i][i] = 1 is a self-loop — skip it; and since the matrix is symmetric, only the upper (or lower) triangle needs scanning in union-find.
Treating rows as an edge list of pairs. It’s an adjacency matrix: neighbors of i are column indices j where the entry is 1, not literal [i, j] pairs.
Counting edges rather than starts/merges. The answer is the number of components — new traversals started, or n minus successful unions.
Forgetting symmetry in DFS/BFS is fine (visited guards it), but double-decrementing in union-find is not — only a successful merge reduces the count.

Pattern takeaway

An adjacency matrix version of connected-components counting: the algorithm is unchanged (DFS/BFS flood fill or union-find), only the neighbor lookup differs — scan a row for the 1s. Dense-matrix input forces O(n²) regardless of method, so pick whichever reads cleanest; union-find shines when you’d otherwise merge groups incrementally.