Time complexity:
, since we are traversing all the cell in the grid
Space complexity:
, for using additional visited[][] arary
Solution using depth first search traversal of the matrix/graph
class Solution {
public int numIslands(char[][] grid) {
//we can use depth first search for this
int visited[][] = new int[grid.length][grid[0].length];
int count =0;
for(int i =0;i<grid.length;i++){
for(int j =0;j<grid[0].length;j++){
if(grid[i][j] =='1' && visited[i][j] ==0){
traverse(i,j,grid,visited);//recursively visited all the connected cells
count++;//increment the island count
}
}
}
return count;
}
public void traverse(int i, int j ,char grid[][] ,int visited[][]){
//base case
if(i <0 || j<0 || i>=grid.length || j>=grid[0].length || visited[i][j] ==1 || grid[i][j]!='1') return;
visited[i][j] =1;// mark the cell visited
int dirs[][] = {{0,-1},{0,1},{-1,0},{1,0}};
for(int dir[] : dirs){
int in = i + dir[0];
int jn = j + dir[1];
traverse(in,jn,grid,visited);
}
}
}
Top comments (0)