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]] ))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
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]] ))