DEV Community

Prashant Mishra
Prashant Mishra

Posted on

Number of islands

Problem

Time complexity: O(MN)O(M*N) , since we are traversing all the cell in the grid
Space complexity: O(MN)O(M*N) , 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);
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)