547 · Number of Provinces

Given an n × n adjacency matrix isConnected where isConnected[i][j] = 1 indicates a direct connection between city i and city j. Count the total number of connected components (provinces).

Simulation & Graph View

idle

INVARIANT Connected Component Invariant: Every unvisited city in the outer loop 0..n-1 marks the discovery of a brand new province (+1). A full DFS/BFS traversal from that city labels all transitively reachable cities as visited. Total work is O(n²) matrix scans and O(n) space.

Adjacency Matrix

Province Clusters

Provinces:0

Outer Loop i:-

Active City:-

Visited:[]

Press Run to begin.

0 / 0

Java 21 Solution

INTERVIEW SCRIPT

How to Explain Number of Provinces to an Interviewer

1. Graph Modeling

"This problem is classic undirected connected components. The vertices are the $n$ cities, and the adjacency matrix gives the edges directly."

2. Outer Loop Component Counting

"We maintain a boolean visited[n] array. We iterate $i$ from 0 to $n-1$. If city $i$ is not visited, it belongs to a new province: increment count++ and launch DFS from $i$."

3. DFS Mechanics on Matrix

"Inside dfs(u), mark visited[u] = true. Then iterate through all potential neighbors $v$ from 0 to $n-1$. If isConnected[u][v] == 1 && !visited[v], recursively explore $v$."

4. Complexity Analysis

"Time complexity is $O(n^2)$ because we check every cell in the $n \times n$ matrix. Space complexity is $O(n)$ for the visited array and recursion stack depth."