Number of Provinces

MediumGraphs · Union Find🧩 Union-Find LeetCode #547 ↗Updated Oct 30, 2026

Problem

There are n cities and a symmetric adjacency matrix isConnected, where isConnected[i][j] = 1 means cities i and j are directly linked. Cities linked directly or through other cities form one province. Return how many provinces there are.

Input[[1,1,0],[1,1,0],[0,0,1]]Output2

Input[[1,0,0],[0,1,0],[0,0,1]]Output3

1 ≤ n ≤ 200 · isConnected[i][j] ∈ {0,1} · isConnected[i][i] = 1 · symmetric

Try it yourself

Java

class Solution {
    public int findCircleNum(int[][] isConnected) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

A province is a connected component. Either flood-fill each unvisited city (each fill = one province) or start with n singleton sets and decrement the count on every union that merges two different sets.

PatternUnion-Find

Instinct Items get grouped by "connected", "same as" or "shares a" links and you keep asking which group something is in: merge sets with Union-Find.

Memory hack Find your boss, merge the bosses; squash the chain (path compression) and hang the short tree under the tall one (rank).

Open the Union-Find guide →

Approaches

Brute ForceTransitive Closure (Floyd–Warshall)

Time O(n³)Space O(n²)

Compute full reachability: i reaches j if it reaches some k that reaches j. Then count the cities that are the smallest index of their province (no smaller city reaches them).

Java

public int findCircleNum(int[][] isConnected) {
    int n = isConnected.length;
    boolean[][] reach = new boolean[n][n];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) reach[i][j] = isConnected[i][j] == 1;
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            if (reach[i][k])
                for (int j = 0; j < n; j++) if (reach[k][j]) reach[i][j] = true;
    int provinces = 0;
    for (int i = 0; i < n; i++) {
        boolean first = true; // i is the smallest city of its province
        for (int j = 0; j < i; j++) if (reach[j][i]) { first = false; break; }
        if (first) provinces++;
    }
    return provinces;
}

Answers every reachability query, but cubic time is overkill for a count.

BetterDFS Flood Fill

Time O(n²)Space O(n)

Scan cities; each unvisited city starts a new province, and a DFS marks every city reachable from it. Each city is visited once and each DFS step scans one matrix row, so total work is n².

Java

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]) {
            dfs(isConnected, visited, i);
            provinces++;
        }
    }
    return provinces;
}
private void dfs(int[][] isConnected, boolean[] visited, int city) {
    visited[city] = true;
    for (int j = 0; j < isConnected.length; j++)
        if (isConnected[city][j] == 1 && !visited[j]) dfs(isConnected, visited, j);
}

Optimal time for a matrix input; recursion depth up to n.

OptimalUnion-Find (Rank + Path Compression)

Time O(n²·α(n))Space O(n)

Start with n provinces, one per city. For each edge (i, j), union their sets; a successful merge removes one province. Union by rank + path halving make each operation nearly O(1) (α = inverse Ackermann).

Java

public int findCircleNum(int[][] isConnected) {
    int n = isConnected.length, provinces = n;
    int[] parent = new int[n], rank = 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 && union(parent, rank, i, j)) provinces--;
    return provinces;
}
private int find(int[] parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]]; // path halving
        x = parent[x];
    }
    return x;
}
private boolean union(int[] parent, int[] rank, int a, int b) {
    int ra = find(parent, a), rb = find(parent, b);
    if (ra == rb) return false; // already in the same province
    if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }
    parent[rb] = ra;
    if (rank[ra] == rank[rb]) rank[ra]++;
    return true;
}

Matches DFS in practice (α(n) ≤ 4), iterative, and supports edges arriving online.

Pro tip

Only scan j > i — the matrix is symmetric, so the lower half repeats the same edges.

At a glance

Level	Approach	Time	Space
Brute Force	Transitive Closure (Floyd–Warshall)	`O(n³)`	`O(n²)`
Better	DFS Flood Fill	`O(n²)`	`O(n)`
Optimal	Union-Find (Rank + Path Compression)	`O(n²·α(n))`	`O(n)`

Common pitfalls

Counting direct links instead of components — friends of friends count.
Decrementing on every edge, not only on a successful merge.
Treating the input as an edge list — it is an n×n matrix.

Interview tips

Say “count connected components” — then pick DFS or Union-Find.
Explain why both are O(n²): the matrix itself has n² cells.
Mention Union-Find shines when edges arrive dynamically.

Pattern

Union-Find / connected components → grouping items by transitive “is connected to” relations.

My notes saved in this browser