Below is my code to find the max area of islands but for some reason it kept failing this test case: [[1],[1]]

Im not entirely sure whats wrong and Ive been thinking to no avail of a possible solution using this method. It was thinking a possible reason why this code is not working properly is because of the synchronous nature of JS when the dfs() is called in the for loop at the bottom.

var maxAreaOfIsland = function(grid) {
        let maxArea = 0
    let currArea = 0

    let dirs = [
        [0,1],
        [1,0],
        [-1,0],
        [0,-1]
    ]

    function dfs(r,c){
        if(grid[r][c] === 0) return
        
        currArea  
        grid[r][c] = 0
        for(let [row,col] of dirs){
            let nr = r row
            let nc = c col
            if(nr<0 || nc< 0|| nr >= grid.length|| nc >= grid[0].length){
                return
            }
            dfs(nr,nc)
        }
    }

    for(let i = 0; i < grid.length; i  ){
        for(let j = 0; j< grid[0].length; j  ){
            if(grid[i][j] === 1){
                
                currArea = 0
                dfs(i,j)
                if(currArea > maxArea){
                    maxArea = currArea
                }
            }
        }
    }

    return maxArea
};

console.log(maxAreaOfIsland( [[1],[1]] ))

CodePudding user response：

It looks as if the dfs function is meant search around a non-zero location, incrementing currArea as it finds more non-zeros, and taking care not to run off the edge of the matrix. The return in that boundary check, however, gives up the search when it should just continue. One change, marked with a comment...

var maxAreaOfIsland = function(grid) {
        let maxArea = 0
    let currArea = 0

    let dirs = [
        [0,1],
        [1,0],
        [-1,0],
        [0,-1]
    ]

    function dfs(r,c){
        if(grid[r][c] === 0) return
        
        currArea  
        grid[r][c] = 0
        for(let [row,col] of dirs){
            let nr = r row
            let nc = c col
            if(nr<0 || nc< 0|| nr >= grid.length|| nc >= grid[0].length){
                continue;  // <-- notice, we keep searching
            }
            dfs(nr,nc)
        }
    }

    for(let i = 0; i < grid.length; i  ){
        for(let j = 0; j< grid[0].length; j  ){
            if(grid[i][j] === 1){
                
                currArea = 0
                dfs(i,j)
                if(currArea > maxArea){
                    maxArea = currArea
                }
            }
        }
    }

    return maxArea
};

console.log(maxAreaOfIsland( [[1],[1]] ))

CodePudding user response：

Try this: I guess you need to check if the cell is valid in grid before going forward.

var maxAreaOfIsland = function(grid) {
        let maxArea = 0
    let currArea = 0

    let dirs = [
        [0,1],
        [1,0],
        [-1,0],
        [0,-1]
    ]

    function dfs(r,c){
        if(r<0 || c< 0|| r >= grid.length|| c >= grid[0].length)
                return
        if(grid[r][c] === 0) return
        
        currArea  
        grid[r][c] = 0
        for(let [row,col] of dirs){
            let nr = r row
            let nc = c col
            dfs(nr,nc)
        }
    }

    for(let i = 0; i < grid.length; i  ){
        for(let j = 0; j< grid[0].length; j  ){
            if(grid[i][j] === 1){
                
                currArea = 0
                dfs(i,j)
                if(currArea > maxArea){
                    maxArea = currArea
                }
            }
        }
    }

    return maxArea
};

console.log(maxAreaOfIsland( [[1],[1]] ))

I recomend using C as the same code will take 8 time less compared to JS