Skip to content

Instantly share code, notes, and snippets.

@SuryaPratapK

SuryaPratapK/Number of islands

Created April 17, 2020 13:58
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save SuryaPratapK/a494ad5194ea33ee83b343698c1fa98e to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save SuryaPratapK/a494ad5194ea33ee83b343698c1fa98e to your computer and use it in GitHub Desktop.
Download ZIP
Raw
Number of islands
class Solution {
void mark_current_island(vector<vector<char>> &matrix,int x,int y,int r,int c)
{
if(x<0 || x>=r || y<0 || y>=c || matrix[x][y]!='1') //Boundary case for matrix
return;
//Mark current cell as visited
matrix[x][y] = '2';
//Make recursive call in all 4 adjacent directions
mark_current_island(matrix,x+1,y,r,c); //DOWN
mark_current_island(matrix,x,y+1,r,c); //RIGHT
mark_current_island(matrix,x-1,y,r,c); //TOP
mark_current_island(matrix,x,y-1,r,c); //LEFT
}
public:
int numIslands(vector<vector<char>>& grid) {
//For FAST I/O
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int rows = grid.size();
if(rows==0) //Empty grid boundary case
return 0;
int cols = grid[0].size();
//Iterate for all cells of the array
int no_of_islands = 0;
for(int i=0;i<rows;++i)
{
for(int j=0;j<cols;++j)
{
if(grid[i][j]=='1')
{
mark_current_island(grid,i,j,rows,cols);
no_of_islands += 1;
}
}
}
return no_of_islands;
}
};
@kru2710shna
Copy link

kru2710shna commented Jul 8, 2023

Perfect Explanation "Here is the Py Code for Folks "
class Solution:
def mark_current_island(self, matrix, x, y, r, c):
if x < 0 or x >= r or y < 0 or y >= c or matrix[x][y] != '1':
return

    # Mark current cell as visited
    matrix[x][y] = '2'
    
    # Make recursive call in all 4 adjacent directions
    self.mark_current_island(matrix, x + 1, y, r, c)  # DOWN
    self.mark_current_island(matrix, x, y + 1, r, c)  # RIGHT
    self.mark_current_island(matrix, x - 1, y, r, c)  # TOP
    self.mark_current_island(matrix, x, y - 1, r, c)  # LEFT

def numIslands(self, grid):
    rows = len(grid)
    if rows == 0:  # Empty grid boundary case
        return 0
    cols = len(grid[0])

    # Iterate for all cells of the array
    no_of_islands = 0
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == '1':
                self.mark_current_island(grid, i, j, rows, cols)
                no_of_islands += 1

    return no_of_islands

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment