Start practising

Number of Provinces

Medium Graphs Connected Components Original on LeetCode

Number of Provinces is a medium graphs problem solved with the connected components pattern. The best approach, union-find (disjoint set), runs in O(n² · α(n)) time and O(n) space. Below are 2 approaches in Java, from dfs / bfs counting components up.

Problem

There are n cities. isConnected[i][j] = 1 means city i and city j are directly connected. A province is a group of cities connected directly or indirectly. Return the number of provinces.

The sheet’s note: count connected components with DFS first, then with BFS.

Examples

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; the matrix is symmetric with 1s on the diagonal.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
DFS / BFS counting componentsO(n²)O(n)
Union-Find (disjoint set)O(n² · α(n))O(n)

1DFS / BFS counting components

TimeO(n²)The adjacency matrix has n² entries.
SpaceO(n)

Loop over cities. When a city is unvisited, start a DFS that marks every city reachable from it and count one province.

  1. For each i: if not seen, count++ and dfs(i).
  2. dfs(u): mark; for each v with isConnected[u][v] == 1 and not seen, dfs(v).
Java
class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length, count = 0;
        boolean[] seen = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (seen[i]) continue;
            count++;
            dfs(isConnected, i, seen);
        }
        return count;
    }

    private void dfs(int[][] g, int u, boolean[] seen) {
        seen[u] = true;
        for (int v = 0; v < g.length; v++) if (g[u][v] == 1 && !seen[v]) dfs(g, v, seen);
    }
}

2Union-Find (disjoint set)

TimeO(n² · α(n))α is the inverse Ackermann function, effectively constant.
SpaceO(n)

Start with n separate sets. Union the two cities of every connection; each successful union removes one set. The number of sets left is the number of provinces.

  1. parent[i] = i; count = n.
  2. For each i < j with a connection: if find(i) != find(j), union them and count--.
Java
class Solution {
    private int[] parent;

    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length, count = n;
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                if (isConnected[i][j] == 1) {
                    int a = find(i), b = find(j);
                    if (a != b) { parent[a] = b; count--; }
                }
        return count;
    }

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

Edge cases to test

  • Every city isolated
  • Everything connected

Hints

Hint 1

Each DFS started from an unvisited city marks one whole province.

FAQ

What is the best time complexity for Number of Provinces?

Union-Find (disjoint set) runs in O(n² · α(n)) time and O(n) extra space. α is the inverse Ackermann function, effectively constant.

Which pattern does Number of Provinces use?

It is a graphs problem that uses the connected components pattern. Other problems with the same pattern: Number of Islands.

Is there a brute force solution for Number of Provinces?

Yes. DFS / BFS counting components takes O(n²) time and O(n) space. Loop over cities.

Which edge cases should I test for Number of Provinces?

Every city isolated; Everything connected.