Algorithmic approach to Java solution


  • 0
    L

    If you are wondering about the algorithm then it is like starting with one unvisited node and traverse the entire possible 1s from that location and mark all of the visited places. Essentially it is like Circle of friends problem. Here is the code:

        public int numIslands(char[][] grid) {
            int count=0;
            for(int i=0;i<grid.length;i++) {
                for(int j=0;j<grid[i].length;j++) {
                    if(grid[i][j]=='1') {
                        count++;
                        grid[i][j]='x';//mark visited.
                        dfs(grid,i,j);
                    }
                }
            }
            return count;
        }
        
        void dfs(char[][] grid,int i, int j) {
            //go right.
            if(j+1<grid[i].length && grid[i][j+1]=='1') {
                //Mark it visited.
                grid[i][j+1]='x';
                dfs(grid,i,j+1);
            }
            //go left.
            if(j-1>=0 && grid[i][j-1]=='1') {
                //Mark it visited.
                grid[i][j-1]='x';
                dfs(grid,i,j-1);
            }
            //go up.
            if(i-1>=0 && grid[i-1][j]=='1') {
                //Mark it visited.
                grid[i-1][j]='x';
                dfs(grid,i-1,j);
            }
            //go down.
            if(i+1<grid.length && grid[i+1][j]=='1') {
                //Mark it visited.
                grid[i+1][j]='x';
                dfs(grid,i+1,j);
            }
        }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.