## DEV Community is a community of 887,564 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Sunbeom Kweon (Ben)

Posted on • Updated on

# 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.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][curr] = '0';
q.pop();
for (auto v:dir){
int newCol = curr + v;
int newRow = curr + v;
if (newCol < 0 || newRow < 0 || newCol >= grid.size() || newRow >= grid.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][curr] = '0';
for (auto v:dir){
int newCol = curr + v;
int newRow = curr + v;
if (newCol < 0 || newRow < 0 || newCol >= grid.size() || newRow >= grid.size() || grid[newCol][newRow] == '0'){
continue;
} else {
vector<int> nextPos = {newCol, newRow};
grid[curr][curr] = '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.