Free lesson · DSA Mastery - Interview Prep, End to End

Number of Provinces

Hard10 min readdsagraphs

Number of Provinces

Number of Provinces is the first direct application of Union Find: given an n × n matrix where isConnected[i][j] == 1 means cities i and j are directly connected, count the number of provinces - groups of cities connected directly or indirectly. The technique is textbook Union Find - union every directly-connected pair of cities, then count the distinct sets (the provinces). It cements the core template (elements = cities, union rule = direct connection, answer = set count) on a clean connected-components problem, and shows how Union Find counts components by tracking the number of disjoint sets as unions merge them. We present Union Find (canonical) and DFS connected-components (alternative).

The insight: a province is a connected component of cities. Union Find computes components by starting with n singleton sets (each city its own province) and merging whenever two cities are directly connected. Each successful merge reduces the province count by one. After processing the connection matrix, the number of disjoint sets is the number of provinces. This is the canonical "elements = nodes, union rule = edge, answer = set count" template - the cleanest first application of the data structure.

The Problem

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.

A province is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an n × n matrix isConnected where isConnected[i][j] = 1 if the i-th city and the j-th city are directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of provinces.

Example 1:

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

Explanation: Cities 0 and 1 are connected (one province); city 2 is alone (another). Total 2.

Example 2:

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

Explanation: No city connects to another; three separate provinces.

Constraints:

1 <= n <= 200
n == isConnected.length == isConnected[i].length
isConnected[i][j] is 1 or 0; isConnected[i][i] == 1; isConnected[i][j] == isConnected[j][i].

Approaches Overview

#	Approach	Time	Space	Verdict
1	Union Find (union connected cities, count sets)	O(n² · α(n))	O(n)	Canonical
2	DFS/BFS connected components	O(n²)	O(n)	Alternative

Union Find unions every directly-connected city pair from the matrix, then returns the number of disjoint sets - the provinces. DFS/BFS instead scans for unvisited cities, running a traversal from each to mark its whole component, counting the traversals. Both scan the n² matrix; Union Find's operations are near-constant. Both are valid; Union Find is the canonical expression of "merge connected groups, count the result," and previews the dynamic-connectivity problems ahead.

Approach 1: Union Find - Canonical

The Idea

Initialize a DSU over the n cities (n provinces initially). Scan the upper triangle of the matrix; for each pair (i, j) with isConnected[i][j] == 1, union(i, j) - merging their provinces (a successful merge decrements the count). After processing all connections, the DSU's set count is the number of provinces.

Logic Flowchart

graph TD
    A["DSU over n cities; count = n"] --> B["for each pair i < j"]
    B --> C{"isConnected[i][j] == 1?"}
    C -->|Yes| D["union(i, j): if merged, count--"]
    C -->|No| B
    D --> B
    B --> E["return count (number of provinces)"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows Number of Provinces by Union Find. Starting with each city as its own province, every directly-connected pair is unioned, decrementing the count on each merge, and the final count is the number of provinces.

Code

public static int findCircleNum(int[][] isConnected) {
    int n = isConnected.length;
    int[] parent = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i;     // each city its own province
    int count = n;

    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)            // upper triangle (symmetric matrix)
            if (isConnected[i][j] == 1) {
                int ri = find(parent, i), rj = find(parent, j);
                if (ri != rj) { parent[ri] = rj; count--; }   // merge → one fewer province
            }
    return count;
}

private static int find(int[] parent, int x) {
    while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }  // path compression
    return x;
}

// Usage:
// findCircleNum([[1,1,0],[1,1,0],[0,0,1]]) -> 2
// findCircleNum([[1,0,0],[0,1,0],[0,0,1]]) -> 3

This Java code counts provinces with Union Find: starting from n cities, it unions every directly-connected pair using path compression, decrementing the count on each merge, and returns the number of disjoint sets.

Step-by-Step Walkthrough

A frame-by-frame trace on Example 1, [[1,1,0],[1,1,0],[0,0,1]]:

graph LR
    F0["DSU: parent=[0,1,2], count=3"]
    F1["pair (0,1): isConnected=1 → union(0,1). roots differ → merge. count=2"]
    F2["pair (0,2): 0. pair (1,2): 0 → no merges"]
    F3["count = 2 provinces ({0,1} and {2})"]
    F0 --> F1 --> F2 --> F3

    style F0 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F1 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F2 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough counts provinces: cities zero and one are connected and merged into one province, while city two stays separate, giving two provinces.

Result: 2.

Complexity

Time: O(n² · α(n)) - scanning the matrix dominates; unions are near-constant. Space: O(n) for the parent array.

Approach 2: DFS Connected Components - Alternative

The Idea

Treat the matrix as an adjacency matrix. For each unvisited city, run a DFS that visits its entire connected component (marking cities visited), and increment a province counter. The number of DFS launches equals the number of provinces - the same connected-component-counting pattern as Number of Islands.

Code

public static int findCircleNumDFS(int[][] isConnected) {
    int n = isConnected.length;
    boolean[] visited = new boolean[n];
    int provinces = 0;
    for (int i = 0; i < n; i++)
        if (!visited[i]) { dfs(isConnected, visited, i, n); provinces++; }   // one per component
    return provinces;
}

private static void dfs(int[][] g, boolean[] visited, int city, int n) {
    visited[city] = true;
    for (int next = 0; next < n; next++)
        if (g[city][next] == 1 && !visited[next]) dfs(g, visited, next, n);
}

// Usage: findCircleNumDFS([[1,1,0],[1,1,0],[0,0,1]]) -> 2

This Java code counts provinces with DFS: it launches a traversal from each unvisited city to mark its whole component, counting the launches as the number of provinces.

Complexity

Time: O(n²) - each matrix cell examined once. Space: O(n) for visited and recursion.

Complexity Comparison

Approach	Time	Space	Key Idea
Union Find	O(n² · α(n))	O(n)	Union connected cities; count disjoint sets
DFS connected components	O(n²)	O(n)	Launch a DFS per unvisited city; count launches

Both count connected components of the city graph. Union Find merges connected cities and reports the number of disjoint sets - the cleanest expression of "group the connected things, count the groups," and the natural choice when connectivity is dynamic. DFS launches one traversal per component (the Number of Islands pattern). Both O(n²) here (dominated by the matrix scan); Union Find is canonical for this sub-group's connectivity theme.

Variations & Follow-ups

How does Union Find count components, and why does each merge decrement the count?

Union Find tracks the number of disjoint sets directly. You start with count = n - every city is its own singleton set, i.e., n provinces (each city trivially its own province before any connections). Each time you process a connection (i, j) and the two cities are in different sets, union merges them into one set, reducing the total number of sets by exactly one - so you decrement count. If the two cities are already in the same set (some prior chain of connections linked them), the union does nothing and count is unchanged. After processing all connections, count is the number of disjoint sets remaining, which is exactly the number of provinces (connected components). This "start at n, decrement on each successful merge" technique is the standard Union Find way to count components - far simpler than re-deriving components afterward. It works because every real merge reduces the component count by one, and the invariant count == number of current disjoint sets is maintained throughout. Compare this to DFS counting (launch a traversal per unvisited node, count launches): Union Find's count emerges incrementally from the merges, which is why it's the natural fit when connections arrive over time and you want the component count after each - you just read count.

How does this instantiate the Union Find template?

Number of Provinces is the cleanest instance of the four-step template from the introduction. Elements: the n cities (indices 0..n-1). Union rule: union cities i and j whenever isConnected[i][j] == 1 - direct connection is the merge condition. Process: scan the connection matrix, performing a union for each 1. Answer: the number of disjoint sets is the number of provinces. There's no twist - the elements are obvious (cities), the union rule is explicit (the matrix entries), and the question is a direct component count. This makes it the ideal first application: it exercises the template without the modeling subtlety that later problems add (where the elements or union rule are non-obvious). Recognizing the template here - "I have things, a rule for when two things are in the same group, and I want the group count" → Union Find - builds the reflex you'll apply when the elements are accounts (merge by shared email), grid cells (merge adjacent land), or equation variables (merge by an equation). The skill the sub-group develops is spotting the elements and the union rule; Number of Provinces presents both plainly, anchoring the pattern before the harder modeling problems.

Why scan only the upper triangle of the matrix, and why does symmetry matter?

The connection matrix is symmetric - isConnected[i][j] == isConnected[j][i] - because connection is mutual (if city i connects to j, then j connects to i). So the lower triangle is a mirror of the upper triangle, carrying no new information. Scanning only the upper triangle (j > i) processes each city pair exactly once, avoiding redundant unions of (i, j) and then (j, i) (which would be harmless but wasteful). The diagonal (isConnected[i][i] == 1, a city connected to itself) is also skipped - a self-connection is meaningless for merging (unioning a city with itself does nothing). So iterating i from 0 to n-1 and j from i+1 to n-1 covers every distinct pair once, cleanly. This is a minor efficiency and clarity point, not a correctness requirement (scanning the full matrix would give the same answer, just doing each union twice). It reflects a good habit: when data has symmetry, exploit it to avoid redundant work. The symmetry here also confirms the graph is undirected (connections have no direction), which is why Union Find - a structure for undirected connectivity - is the apt tool. Directed connectivity would need different machinery (like strongly-connected-components algorithms).

When would you prefer Union Find over DFS for this, and vice versa?

For this static problem - a fixed connection matrix, count provinces once - DFS and Union Find are equally good: both O(n²) (dominated by reading the matrix), both simple. The DFS approach (launch a traversal per unvisited city, count launches) is the Number of Islands pattern and perfectly natural. Union Find becomes preferable when the problem is dynamic or query-heavy: if connections are added incrementally and you must report the province count after each addition, Union Find updates in near-O(1) per connection, while DFS would re-scan the whole graph each time (O(n²) per query). Union Find also shines when you need repeated "are these two connected?" queries interleaved with merges - each query is a near-O(1) find. So the decision mirrors the introduction's guidance: static, one-shot connectivity → DFS/BFS is fine; dynamic or repeatedly-queried connectivity → Union Find. Number of Provinces is static, so either works, but it's the right place to learn Union Find because the structure is simple enough to see clearly. Its dynamic cousins (Number of Islands II, where land is added over time; or any "after each edge, how many components?" problem) are where Union Find becomes essential, and they're previewed by mastering the static case here.

What about edge cases?

All cities connected (one big province): All merge into one set; count 1.
No connections beyond self (Example 2): No merges; count stays n.
Single city (n == 1): One province.
Chain of connections (0-1-2-...): All transitively merged into one province.
Two separate clusters (Example 1): Two disjoint sets; count 2.

Common Interview Pitfalls

Not decrementing count only on a successful merge. If the cities are already in the same set, don't decrement; check ri != rj.
Scanning the full matrix redundantly. Use the upper triangle (j > i); the matrix is symmetric.
Forgetting path compression / union optimization. For small n it's fine, but include it for the near-constant guarantee and good habits.
Confusing "directly connected" with the final answer. Provinces count transitive connectivity (components), which the merges build up.

Why This Topic Matters

Number of Provinces is the cleanest Union Find component-count application: elements are cities, the union rule is direct connection, and the answer is the number of disjoint sets - computed by starting at n and decrementing on each successful merge. It cements the four-step template (elements, union rule, process, count) and the "track the set count as unions merge" technique, anchoring the pattern before the problems where the elements and union rule are less obvious.

The next topic, Redundant Connection, applies Union Find to cycle detection: given a graph that started as a tree (n nodes, n-1 edges, connected, acyclic) but had one extra edge added, find that redundant edge - the one that creates a cycle. The technique processes edges in order with Union Find: for each edge, if its two endpoints are already in the same set, that edge closes a cycle and is the redundant one; otherwise union them. It cements Union Find's cycle-detection use - "an edge between already-connected nodes forms a cycle" - the second of the three classic Union Find applications, and a beautifully direct one-pass solution.

Back to DSA Mastery - Interview Prep, End to End