Q4 Number of Islands - LeetCode 200
Sat Apr 08 2023 16:24:47 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
class Solution {
public int numIslands(char[][] grid) {
/* we treat this like a question of graph to find components which are
islands in this case
*/
boolean visited[][] = new boolean [grid.length][grid[0].length];
int component = 0;
//dfs from every node
for(int i = 0 ; i < grid.length ;i++){
for(int j = 0 ; j < grid[0].length ;j++){
//if it is land and visited is false
if(grid[i][j] == '1' && visited[i][j] == false){
dfs(grid , i , j , visited);
component++;
}
}
}
return component;
}
public void dfs (char[][]grid , int i , int j , boolean[][] visited){
//base case
if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length
|| visited[i][j] == true || grid[i][j] == '0')
return ;
visited[i][j] = true;
//going in all 4 directions
dfs(grid , i , j+1 , visited);
dfs(grid , i+1 , j , visited);
dfs(grid , i-1 , j , visited);
dfs(grid , i , j-1 , visited);
}
}
content_copyCOPY
https://leetcode.com/problems/number-of-islands/
Comments