Simple Recursive Solution in Java


  • 0
    J
    public class Solution { 
        int n, m=0;
        public int numIslands(char[][] grid) {
            int count = 0;
            n = grid.length;
            if(n>0)
                m = grid[0].length;            
            for(int i=0; i<n; i++){
                for(int j=0; j<m; j++){
                    if(grid[i][j] == '1'){
                        markvisited(grid, i, j);
                        count++;
                    }
                }
            }
            return count;
        }
    
        void markvisited(char[][] grid, int i, int j){
            grid[i][j] = '0';
            if(i>0 && grid[i-1][j]=='1'){
                markvisited(grid, i-1, j);
            }
            if(j>0 && grid[i][j-1]=='1'){
                markvisited(grid, i, j-1);
            }
            if(i<n-1 && grid[i+1][j]=='1'){
                markvisited(grid, i+1, j);
            }
            if(j<m-1 && grid[i][j+1]=='1'){
                markvisited(grid, i, j+1);
            }
        }  
    }
    

    Explanation:
    Find '1' in matrix. For every '1' found, make to '0'.
    Similarly check for remaining '1's.

    All the cases to be considered: Left, Right, Up and Down.
    Following Case also needs: Left and Up Direction Traversal.

    ["11100",
     "00100",
     "10100",
     "11100"]
    

Log in to reply
 

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