A method in Java


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

  • 0
    S

    great solution. Time complexity of O(n^2) right?


  • 1

    @saneGuy I think so... Did you come up with better ideas? Wait for that :)


  • 0
    S

    @Linzhuo this is a clean solution :) thanks for sharing. I will share if i get a better solution .


Log in to reply
 

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