Number of Provinces

Medium Problem 110 of 151 Java and Python

Problem

There are n cities. isConnected[i][j] = 1 if cities i and j are directly connected. Connection is transitive: if a connects to b and b to c, then a and c are in the same province.

Return the number of provinces (groups of connected cities).

Example 1

Input: isConnected = [[1, 1, 0], [1, 1, 0], [0, 0, 1]]
Output: 2

Example 2

Input: isConnected = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
Output: 3

Constraints

1 ≤ n ≤ 200
isConnected is symmetric and isConnected[i][i] = 1.

Explanation

Provinces are connected components. Either run a DFS from each unvisited city and count the runs, or use Union-Find: start with n separate groups and merge the two groups of every connected pair; each successful merge reduces the count by one.

Approach 1 · Better

DFS over the matrix

Time O(n²)
Space O(n)

Each DFS from an unvisited city marks its whole province.

For each unvisited city: count a province and DFS.
dfs(i): mark i; recurse into every unvisited j with isConnected[i][j] == 1.

Java

class Solution {
    public int findCircleNum(int[][] isConnected) {
        boolean[] visited = new boolean[isConnected.length];
        int provinces = 0;
        for (int i = 0; i < isConnected.length; i++) {
            if (!visited[i]) {
                provinces++;
                dfs(isConnected, i, visited);
            }
        }
        return provinces;
    }

    private void dfs(int[][] isConnected, int i, boolean[] visited) {
        visited[i] = true;
        for (int j = 0; j < isConnected.length; j++) {
            if (isConnected[i][j] == 1 && !visited[j]) {
                dfs(isConnected, j, visited);
            }
        }
    }
}

Python

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

        def dfs(i):
            visited[i] = True
            for j in range(n):
                if isConnected[i][j] and not visited[j]:
                    dfs(j)

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

Approach 2 · Optimal

Union-Find

Time O(n² · α(n)), α ≈ constant
Space O(n)

Keep a parent array where each group points to a root. Union every connected pair; count successful unions.

find(x): follow parents to the root, compressing the path.
union(a, b): if the roots differ, link one to the other and return true.
Start with n provinces and subtract one per successful union.

Java

class Solution {
    private int[] parent;

    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        int provinces = n;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isConnected[i][j] == 1 && union(i, j)) {
                    provinces--;
                }
            }
        }
        return provinces;
    }

    private int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    private boolean union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA == rootB) {
            return false;
        }
        parent[rootA] = rootB;
        return true;
    }
}

Python

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

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

        provinces = n
        for i in range(n):
            for j in range(i + 1, n):
                if isConnected[i][j]:
                    a, b = find(i), find(j)
                    if a != b:
                        parent[a] = b
                        provinces -= 1
        return provinces

Complexity compared

Approach	Time	Space
Better DFS over the matrix	O(n²)	O(n)
Optimal Union-Find	O(n² · α(n)), α ≈ constant	O(n)

Key takeaways

Union-Find shines when edges arrive one at a time or you need "are these two connected?" queries.
Path compression (parent[x] = parent[parent[x]]) is what keeps find nearly constant.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem