LeetCode Max Area of Island Solution Explained - Java

[@_ParijatChatterjee]

instead of that extra seen boolean, before the return statement in the area function just write grid[r][c] = 0.

[@Bryan-gu5fg]

can u explain why we can use grid[r][c] instead of seen boolean?

[@gabrieltimothy2255]

@@Bryan-gu5fg Firstly by setting already visited grid[r][c] to 0 we can similarly guarantee that our function will not mistakenly count it again as an island on the next iterations (since islands are identified as 1). Secondly, we might prefer to do this instead as it is more efficient in terms of space complexity, i.e. we don't need to allocate space in memory for another 2 dimensional array for 'seen'.

[@juanvibeats3880]

Here's an optimized version in JavaScript, instead of having the seen global variable, we can simply set the 1s equal to 0 once we've viewed them. Got the idea from Nick's video on 'Number of Islands' leetcode problem: /** * @param {number[][]} grid * @return {number} */ var maxAreaOfIsland = function(grid) { let maxArea = 0; for(let i = 0; i < grid.length; i++) { for(let j = 0; j < grid[0].length;j++) { if(grid[i][j] === 1) { let areaOfIsland = dfs(grid,i,j); if(areaOfIsland > maxArea) { maxArea = areaOfIsland; } } } } return maxArea; }; const dfs = (matrix, i, j, area) => { if(i < 0 || j < 0 || i >= matrix.length || j >= matrix[0].length || matrix[i][j] === 0) { return 0; } if(!area) area = 1; area += 1; matrix[i][j] = 0; let up = dfs(matrix, i - 1, j, area); let down = dfs(matrix, i + 1, j, area); let left = dfs(matrix, i, j - 1, area); let right = dfs(matrix, i, j + 1, area); return 1 + up + down + right + left; }

[@alankuo2316]

great explanation!!!

[@vikrant236]

Hey Nick, did you study any other questions too for your tech interviews. If you can share complete list you solved before interview that would be great!

[@zahash1045]

OMG!! HE'S SO GOD DAMN COOL!!!

[@joecamroberon9322]

Can you explain why you are returning 1 + the recursive call?

[@NickWhite]

hey yeah because the cell is valid. If the cell is not valid than the function returns 0 immediately, but if it is valid we add 1 to the total area

[@NickWhite]

if we didn't add 1 at some point than the area would never grow and always be zero

[@yogendramaarisetty]

above recursion is something like this example: f(n) = 1 + f(n-1) { n>=0, f(0) = 0 } lets say n = 4 f(4) = 1 + f(3) f(4) = 1 + (1 + f(2)) f(4) = 1+ (1 + (1 + f(1))) f(4) = 1+(1+(1+(1+f(0)))) f(4) = 4

[@lifehacks9450]

could u pls upload word ladder 2 problem

[@vishaldhanani3942]

It is not working in the test case of [[0],[1]]. Please explain it. Thanks

[@yogendramaarisetty]

I will work!

[@ZEEEDgenx]

Just to check if I'm understanding, we should return 0 on a seen island because, if we don't and we keep recursively visiting that island our area for the max area would go to infinity because it keeps checking its neighbor and its neighbor keeps checking it.

[@yesh5943]

I think we return 0 because the area of a 0 cell is not part of an island and does not contribute to its area.

[@pankajas6448]

time limit exceeded bro :(

[@aryandeshpande1241]

Ayoo

[@msantagiulianab]

"Time Limit Exceeded", time-complexity is too high.