{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsChat
New
BlogPricing
Ctrl + K

Number of Provinces – Solution & Complexity

Interview solutions
/
Number of Provinces

Solution Walkthrough

1. Understand the Goal

  • isConnected is an n x n adjacency matrix over directly-connected cities; "province" means a connected component under the transitive closure of that direct-connection relation (if A-B and B-C are both direct connections, A and C are in the same province even with no direct A-C entry).
  • The answer is just the number of connected components in this graph.

2. Choose the Core Pattern

  • Disjoint-set union (union-find): start with every city in its own set, then union the two endpoints of every direct connection. The final answer is the number of distinct sets remaining.
  • Path compression (flattening each find chain toward the root as you traverse it) and union by rank (attaching the shorter tree under the taller one) keep the amortized cost of each operation nearly constant, which is why DSU beats a plain DFS/BFS-per-node only in code simplicity here, not asymptotics — but it generalizes better to the "incremental connection updates" follow-up.

3. Build the Algorithm

  • Initialize parent[i] = i for every city and a running provinces counter at n (every city starts as its own province).
  • find(x) walks parent pointers to the root, compressing the path along the way so future lookups are faster.
  • union(a, b): find both roots; if they're already equal, this connection is redundant — do nothing and report no merge happened. Otherwise attach the lower-rank root under the higher-rank root (bumping rank on a tie), and report that a merge happened.
  • Scan only the upper triangle of the matrix (col > row, since it's symmetric) and call union for every isConnected[row][col] == 1; decrement provinces only when union reports an actual merge (roots were different) — unioning two cities already in the same province must not double-decrement.

4. Check Edge Cases

  • All cities connected to each other (all 1s): every union after the first in a component reports "already merged," so provinces ends at 1.
  • No city connected to any other except itself (identity matrix): no union ever succeeds, so provinces stays at n.
  • A single city (n == 1): the loop over pairs never runs, and the answer is correctly 1.
  • A chain like 1-2, 2-3 (but no direct 1-3 entry): after unioning (1,2) and (2,3), find(1) == find(3) transitively through path compression, even though the matrix has no direct 1-3 edge.

5. Final Solution and Complexity

  • Time complexity is O(n^2 α(n)).
  • Space complexity is O(n).
def find_circle_num(is_connected: list[list[int]]) -> int:
    n = len(is_connected)
    parent = list(range(n)); rank = [0] * n
    provinces = n
    def find(node):
        while node != parent[node]:
            parent[node] = parent[parent[node]]; node = parent[node]
        return node
    def union(a, b):
        a, b = find(a), find(b)
        if a == b: return False
        if rank[a] < rank[b]: a, b = b, a
        parent[b] = a
        if rank[a] == rank[b]: rank[a] += 1
        return True
    for row in range(n):
        for col in range(row + 1, n):
            if is_connected[row][col] == 1 and union(row, col):
                provinces -= 1
    return provinces

FAQ

See also

Practice Number of Provinces online (run code in the browser)Redundant Connection solution (medium)Clone Graph solution (medium)Course Schedule solution (medium)Network Delay Time solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsContact Us © Monkey SkatesHave kids?