1. Overview
- The approach I used for this problem is Breadth First Search(BFS). Starting from one point, and scanning its up, down, left and right coordinates of the given 2D-array.
2. Struggles
The reason why I decided to write this post is that I found out that a tiny mistake can lead to an inefficient solution, when it comes to the solution using BFS. And I wanted to share this so that I don't make the same mistake during any interviews.
The code with my mistake would give the correct answer, but it will get "Time Limit Exceeded" error on Leetcode.
3. Codes
Main function
int numIslands(vector<vector<char>>& grid) {
if(grid.size() == 0) return 0;
int count = 0;
for (int i = 0; i < grid.size(); i++){
for (int j = 0; j < grid[0].size(); j++){
if(grid[i][j] == '0') {
continue;
} else {
BFS(grid, i, j, count);
}
}
}
return count;
}
Wrong BFS function
void BFS(vector<vector<char>>& grid, int i, int j, int& count){
vector<vector<int>> dir = {{-1,0}, {1,0}, {0,-1}, {0,1}};
queue<vector<int>> q;
vector<int> start = {i, j};
q.push(start);
while(!q.empty()){
vector<int> curr = q.front();
grid[curr[0]][curr[1]] = '0';
q.pop();
for (auto v:dir){
int newCol = curr[0] + v[0];
int newRow = curr[1] + v[1];
if (newCol < 0 || newRow < 0 || newCol >= grid.size() || newRow >= grid[0].size() || grid[newCol][newRow] == '0'){
continue;
} else {
vector<int> nextPos = {newCol, newRow};
q.push(nextPos);
}
}
}
count++;
}
Correct BFS function
static void BFS(vector<vector<char>>& grid, int i, int j, int& count){
vector<vector<int>> dir = {{-1,0}, {1,0}, {0,-1}, {0,1}};
queue<vector<int>> q;
vector<int> start = {i, j};
q.push(start);
while(!q.empty()){
vector<int> curr = q.front();
q.pop();
grid[curr[0]][curr[1]] = '0';
for (auto v:dir){
int newCol = curr[0] + v[0];
int newRow = curr[1] + v[1];
if (newCol < 0 || newRow < 0 || newCol >= grid.size() || newRow >= grid[0].size() || grid[newCol][newRow] == '0'){
continue;
} else {
vector<int> nextPos = {newCol, newRow};
grid[curr[0]][curr[1]] = '0'; // <= Solution
q.push(nextPos);
}
}
}
count++;
}
4. Explanation
Did you see why the first function would cause an error? The reason is that I was not taking advantage of BFS. Since I was not turning '1' to '0' while I was scanning up, down, left and right coordinates, on the next loop, the queue will keep pushing those coordinates that I have already visited, Which will lead my program codes getting Time Limit Exceeded error, even though the answer is going to be the same.
Top comments (0)