https://leetcode.com/problems/number-of-provinces/
I was pretty excited when I solved this problem on my very first try, within only 20/30 minutes, though when I submitted my code, I ended up in 8.43 percentile. I looked at how the fastest solutions approached the problem, and low and behold, the sample top solution is nearly identical to my code, yet it runs 3x faster. I've been comparing the code and can't really point out a substantial enough difference. Both should be equally fast... Can anyone explain the why? If I'm not mistaken it's O(mn) performance in both cases.
The following is my code. It's pretty self-explanatory, so not sure heavy commenting would do any good.
class Solution {
public:
int findCircleNum(vector<vector<int>>& isConnected) {
int components = 0;
vector<bool> visited (isConnected.size(), false);
// go through each row
for (int i = 0; i < isConnected.size(); i++) {
// explore only unvisited items
if (!visited[i]) {
queue<int> q;
q.push(i);
components++;
while (!q.empty()) {
int node = q.front();
q.pop();
visited[node] = true;
// push all direct connections onto the queue so we explore them
for (int j = 0; j < isConnected[0].size(); j++) {
if (isConnected[node][j] == 1 && !visited[j]) {
q.push(j);
}
}
}
}
}
return components;
}
};
and the following is a sample top solution that runs 3x faster than my code.
class Solution {
public:
int findCircleNum(vector<vector<int>>& M) {
if (M.empty()) {
return 0;
}
int count = 0;
vector<bool> visited(M.size());
auto bfs = [&](int student) {
queue<int> q;
q.push(student);
visited[student] = true;
while (!q.empty()) {
auto current = q.front();
cout << "current " << current << endl;
q.pop();
for (int i = 0; i < M.size(); i++) {
if (M[current][i] == 1 and !visited[i]) {
visited[i] = true;
q.push(i);
}
}
}
};
for (int r = 0; r < M.size(); r++) {
if (visited[r] == false) {
count++;
bfs(r);
}
}
return count;
}
};
