Q1) 547. Number of Provinces
💡 Initial Idea & The Mistake
My first instinct was to simply count the rows where the array sum equals 1 (meaning a city is only connected to itself), assuming everything else would naturally hook together into a single province.
The flaw in that logic: I completely overlooked scenarios where you might have multiple distinct, disconnected clusters of cities (e.g., two cities connected to each other, while three other cities form their own separate group).
To fix this, I broke out a notepad, sketched out the graph visually, and realized this was a classic graph traversal problem perfectly suited for Depth-First Search (DFS).
🛠️ Optimized DFS Solution (Java)
In my initial draft, I used an external helper function (allVisit) to scan the visited array repeatedly inside a loop. This added unnecessary overhead. By simply looping through all cities once from 0 to n-1 and triggering a DFS whenever we hit an unvisited city, we can count the provinces much more efficiently.
class Solution {
public int findCircleNum(int[][] isConnected) {
int cities = isConnected.length;
int provinces = 0;
boolean[] visited = new boolean[cities];
// Loop through each city. If it hasn't been visited,
// it represents the start of a new province.
for (int i = 0; i < cities; i++) {
if (!visited[i]) {
dfs(i, visited, isConnected);
provinces++; // Increment the province count
}
}
return provinces;
}
private void dfs(int city, boolean[] visited, int[][] matrix) {
visited[city] = true;
// Visit all adjacent, unvisited cities
for (int i = 0; i < visited.length; i++) {
if (matrix[city][i] == 1 && !visited[i]) {
dfs(i, visited, matrix);
}
}
}
}
Top comments (1)
Hope dev.to adds plag testing and AI content detection. Please don't post AI content very easy to find how much ever you cover up.