Number of Provinces (LeetCode 547)
n cities may be linked by direct connections, and connections chain: if a links to b and b links to c, then a and c count as linked too, even without a direct edge.
A province is one maximal cluster of cities reachable from each other this way, with no city belonging to two clusters.
The input is isConnected, an n x n matrix in which isConnected[i][j] = 1 marks a direct connection between city i and city j (0 otherwise).
Report how many provinces exist in total.
Worked Examples
isConnected = [[1,1,0],[1,1,0],[0,0,1]]20 and 1 are linked; city 2 stands alone. That makes 2 provinces.isConnected = [[1,0,0],[0,1,0],[0,0,1]]3⚖️Formal Constraints & Bounds
1 <= n <= 200n == isConnected.lengthn == isConnected[i].lengthisConnected[i][j]is1or0.isConnected[i][i] == 1isConnected[i][j] == isConnected[j][i]
Core Insight
Every successful union between disjoint roots reduces the total component count by exactly 1.
Real-World Scenario & Production Applications
Telecom regional network partitioning, social network friend cluster count.
Subproblems & Recurrence Decomposition3 Phases
Locate the canonical root of node i, flattening the tree pointer structure during recursion so future lookups execute in O(alpha(N)) nearly constant time.
def find(i):
if parent[i] != i:
parent[i] = find(parent[i]) # Path compression
return parent[i]Step-by-Step Execution Trace Table
| Edge (i, j) | find(i) Root | find(j) Root | Action | Remaining Provinces |
|---|---|---|---|---|
| Initial | - | - | - | 3 |
| (0, 1) = 1 | 0 | 1 | Union(0, 1) | 2 |
| (0, 2) = 0 | 0 | 2 | No connection | 2 |
| (1, 2) = 0 | 0 | 2 | No connection | 2 |
| 1 | parent = list(range(n)) |
| 2 | provinces = n |
| 3 | for i in range(n): |
| 4 | for j in range(i + 1, n): |
| 5 | if isConnected[i][j] and union(i, j): |
| 6 | provinces -= 1 |
| 7 | return provinces |
Conceptual Narrative
Number of Provinces counts connected components in an undirected adjacency matrix. Initializing N independent components and decrementing upon every successful union solves the problem in near-linear time.
🧭 Conceptual Foundation & Pattern Intuition
We are given an symmetric adjacency matrix where isConnected[i][j] == 1 indicates a direct bidirectional link between city and city . A "province" is a maximal connected component of directly or indirectly linked cities.
Instead of running separate graph traversals (BFS/DFS) with visited sets, Disjoint Set Union provides a purely algebraic accounting solution:
- Initialize the system with independent provinces (
count = n), where each city is its own root (parent[i] = i). - Iterate through all pairs with (exploiting upper-triangular symmetry).
- Whenever
isConnected[i][j] == 1, attempt to unite city and city . - If
find(i) != find(j), the two cities belonged to previously separate provinces. Merging them decreases the total province count by exactly 1 (count -= 1). If they already shared a root, no count change occurs.
🤝 The Analogy: Treaty Mergers Among Feudal Kingdoms
Imagine sovereign kingdoms on a continent. At sunrise, there are exactly independent flags flying. Throughout the day, ambassadors sign mutual defense treaties (isConnected[i][j] == 1). When two kingdoms from completely different alliances sign a treaty, their alliances merge into a single commonwealth, and one flag is retired (total independent nations decreases by 1). If two kingdoms that already belong to the same commonwealth sign a treaty, no new land is added and no flags are retired. At sunset, the remaining flag count is the total number of provinces.
🔑 Why It Works
Because dsu.union() returns a boolean indicating whether a genuine merge occurred, tracking component cardinality requires zero post-processing or hash-set deduplication.
Double-checking edges: Checking both
isConnected[i][j]andisConnected[j][i]doubles union operations; scan upper trianglerange(i + 1, n).Forgetting path compression: Omitting
parent[x] = find(parent[x])infind()degrades tree height to , slowing union operations.Counting roots at the end without path compression: Calling
len(set(parent))at the end without callingfind()on all nodes returns uncompressed intermediate parents.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Counting connected components from an adjacency matrix.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: total components equals N minus total successful union operations.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Iterating symmetric matrix twice: only iterate
j > ito avoid redundant comparisons.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I initialize DSU with
nindividual components (provinces = n). For each pair(i, j)whereisConnected[i][j] == 1, I find their roots. Iffind(i) != find(j), I union them and decrementprovinces -= 1. I returnprovinces. Runs in O(N² · α(N)) time andO(N)space."
Complexity & Mathematical Proof
O(N^2 · alpha(N))
Look at the execution steps: Examines N x N adjacency matrix. For each connection where isConnected[i][j] == 1, calls union(i, j) on DSU of size N. Total N^2 edge checks.
O(N) Auxiliary
Look at memory allocations: parent and rank hold N entries each, O(N). find calls itself once per level of a tree, and union by rank keeps every tree at most log2 N + 1 levels tall, so the call stack is O(log N). The answer is one count, O(1).
T(N) = N^2 · O(α(N)) = O(N^2)
Derivation Progression
for i, j ∈ [0, N-1]
Scans all N^2 matrix cells.
if isConnected[i][j]: union(i, j)
Merges connected provinces in O(alpha(N)) time.
count decrements on successful union
Tracks number of disjoint province sets.
Variable Definitions
Number of cities (dimension of N × N adjacency matrix)
Inverse Ackermann function (α ≤ 4)
Memory Architecture & Bounds
O(log N) Recursive find, union by rank
O(N) Parent array of size N
O(1) Province count integer
Boundary Best / Worst Cases
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "directly or indirectly connected", "total number of provinces". Connected component counting on an adjacency matrix. While BFS/DFS work well, DSU provides a stateful mechanism: start with isolated components; every successful union operation decrements the component counter by 1.
. Adjacency matrix . Time budget takes ms.
Symmetric matrix redundancy: only iterate over upper triangular entries where .
Number of Provinces (LeetCode 547)
n cities may be linked by direct connections, and connections chain: if a links to b and b links to c, then a and c count as linked too, even without a direct edge.
A province is one maximal cluster of cities reachable from each other this way, with no city belonging to two clusters.
The input is isConnected, an n x n matrix in which isConnected[i][j] = 1 marks a direct connection between city i and city j (0 otherwise).
Report how many provinces exist in total.
Worked Examples
isConnected = [[1,1,0],[1,1,0],[0,0,1]]20 and 1 are linked; city 2 stands alone. That makes 2 provinces.isConnected = [[1,0,0],[0,1,0],[0,0,1]]3⚖️Formal Constraints & Bounds
1 <= n <= 200n == isConnected.lengthn == isConnected[i].lengthisConnected[i][j]is1or0.isConnected[i][i] == 1isConnected[i][j] == isConnected[j][i]
Core Insight
Every successful union between disjoint roots reduces the total component count by exactly 1.
Real-World Scenario & Production Applications
Telecom regional network partitioning, social network friend cluster count.
Subproblems & Recurrence Decomposition3 Phases
Locate the canonical root of node i, flattening the tree pointer structure during recursion so future lookups execute in O(alpha(N)) nearly constant time.
def find(i):
if parent[i] != i:
parent[i] = find(parent[i]) # Path compression
return parent[i]Step-by-Step Execution Trace Table
| Edge (i, j) | find(i) Root | find(j) Root | Action | Remaining Provinces |
|---|---|---|---|---|
| Initial | - | - | - | 3 |
| (0, 1) = 1 | 0 | 1 | Union(0, 1) | 2 |
| (0, 2) = 0 | 0 | 2 | No connection | 2 |
| (1, 2) = 0 | 0 | 2 | No connection | 2 |
| 1 | parent = list(range(n)) |
| 2 | provinces = n |
| 3 | for i in range(n): |
| 4 | for j in range(i + 1, n): |
| 5 | if isConnected[i][j] and union(i, j): |
| 6 | provinces -= 1 |
| 7 | return provinces |
Conceptual Narrative
Number of Provinces counts connected components in an undirected adjacency matrix. Initializing N independent components and decrementing upon every successful union solves the problem in near-linear time.
🧭 Conceptual Foundation & Pattern Intuition
We are given an symmetric adjacency matrix where isConnected[i][j] == 1 indicates a direct bidirectional link between city and city . A "province" is a maximal connected component of directly or indirectly linked cities.
Instead of running separate graph traversals (BFS/DFS) with visited sets, Disjoint Set Union provides a purely algebraic accounting solution:
- Initialize the system with independent provinces (
count = n), where each city is its own root (parent[i] = i). - Iterate through all pairs with (exploiting upper-triangular symmetry).
- Whenever
isConnected[i][j] == 1, attempt to unite city and city . - If
find(i) != find(j), the two cities belonged to previously separate provinces. Merging them decreases the total province count by exactly 1 (count -= 1). If they already shared a root, no count change occurs.
🤝 The Analogy: Treaty Mergers Among Feudal Kingdoms
Imagine sovereign kingdoms on a continent. At sunrise, there are exactly independent flags flying. Throughout the day, ambassadors sign mutual defense treaties (isConnected[i][j] == 1). When two kingdoms from completely different alliances sign a treaty, their alliances merge into a single commonwealth, and one flag is retired (total independent nations decreases by 1). If two kingdoms that already belong to the same commonwealth sign a treaty, no new land is added and no flags are retired. At sunset, the remaining flag count is the total number of provinces.
🔑 Why It Works
Because dsu.union() returns a boolean indicating whether a genuine merge occurred, tracking component cardinality requires zero post-processing or hash-set deduplication.
Double-checking edges: Checking both
isConnected[i][j]andisConnected[j][i]doubles union operations; scan upper trianglerange(i + 1, n).Forgetting path compression: Omitting
parent[x] = find(parent[x])infind()degrades tree height to , slowing union operations.Counting roots at the end without path compression: Calling
len(set(parent))at the end without callingfind()on all nodes returns uncompressed intermediate parents.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Counting connected components from an adjacency matrix.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: total components equals N minus total successful union operations.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Iterating symmetric matrix twice: only iterate
j > ito avoid redundant comparisons.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I initialize DSU with
nindividual components (provinces = n). For each pair(i, j)whereisConnected[i][j] == 1, I find their roots. Iffind(i) != find(j), I union them and decrementprovinces -= 1. I returnprovinces. Runs in O(N² · α(N)) time andO(N)space."
Complexity & Mathematical Proof
O(N^2 · alpha(N))
Look at the execution steps: Examines N x N adjacency matrix. For each connection where isConnected[i][j] == 1, calls union(i, j) on DSU of size N. Total N^2 edge checks.
O(N) Auxiliary
Look at memory allocations: parent and rank hold N entries each, O(N). find calls itself once per level of a tree, and union by rank keeps every tree at most log2 N + 1 levels tall, so the call stack is O(log N). The answer is one count, O(1).
T(N) = N^2 · O(α(N)) = O(N^2)
Derivation Progression
for i, j ∈ [0, N-1]
Scans all N^2 matrix cells.
if isConnected[i][j]: union(i, j)
Merges connected provinces in O(alpha(N)) time.
count decrements on successful union
Tracks number of disjoint province sets.
Variable Definitions
Number of cities (dimension of N × N adjacency matrix)
Inverse Ackermann function (α ≤ 4)
Memory Architecture & Bounds
O(log N) Recursive find, union by rank
O(N) Parent array of size N
O(1) Province count integer
Boundary Best / Worst Cases
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "directly or indirectly connected", "total number of provinces". Connected component counting on an adjacency matrix. While BFS/DFS work well, DSU provides a stateful mechanism: start with isolated components; every successful union operation decrements the component counter by 1.
. Adjacency matrix . Time budget takes ms.
Symmetric matrix redundancy: only iterate over upper triangular entries where .