DEV Community

Sunbeom Kweon (Ben)
Sunbeom Kweon (Ben)

Posted on • Edited on

[Algorithms] 4 - Number of Islands

#algorithms

Link to the problem

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; }
Enter fullscreen mode Exit fullscreen mode

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++; }
Enter fullscreen mode Exit fullscreen mode

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++; }
Enter fullscreen mode Exit fullscreen mode

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)