Day 17 of 30 Day LeetCode Challenge

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

//fast I/O
static auto x = [](){
return nullptr;

class Solution {

pair<int, int> findNextOne(vector<vector<char>> grid){
for(int i=0;i<grid.size();++i){
for(int j=0;j<grid[i].size();++j){
if(grid[i][j]==’1') return make_pair(i, j);
return make_pair(-1, -1);

void bfs(vector<vector<char>>& grid, int i, int j){
int rowSize = grid.size();
int colSize = grid[0].size();

grid[i][j] = ‘v’; //visited

//bfs on all its neighbours
int r[4] = {-1, 0, 1, 0};
int c[4] = {0, 1, 0, -1};

for(int k=0;k<4;++k){
int newI = i+r[k];
int newJ = j+c[k];
if( (newI>=0&&newI<rowSize)&&(newJ>=0&&newJ<colSize)&&grid[newI][newJ]==’1') bfs(grid, newI, newJ);

int numIslands(vector<vector<char>>& grid) {

int islands = 0;

//method : O(v²) time & O(1) space
//bfs : strongly connected components
pair<int, int> index = findNextOne(grid);



//bfs starting from (index.first, index.second)
bfs(grid, index.first, index.second);

//next connected component
index = findNextOne(grid);

return islands;



We never really grow up, we only learn how to act in public

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store