[Programming Problem] Max Area of Island

[Problem Link]

Algorithm:

  • Loop through universe. Looks for any island element `1` and run recursive algo on it.
  • Recurse: Basically, move top, bottom, left, right. Make sure you change the island element to `currIslandId` so that you don’t end up in an infinite loop. Return 1 + recurse(top) + recurse(bottom) + recurse(left) + recurse(right).
  • Return the max area you’ve seen up-to now.
  • At worst, you will loop through the grid twice (imagine the entire grid being 1’s). Time complexity is O(MN)
/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxAreaOfIsland = function(grid) {
    let currIslandId = 2;
    let currMaxArea = 0;
 
    for (let i = 0 ; i < grid.length ; i++ ) {
        for ( let j = 0 ; j < grid[0].length ; j++ ) {
            if (grid[i][j] === 1) {
                const tmpMaxArea = maxAreaRecursive(grid, currIslandId, i, j);
                currMaxArea = Math.max(currMaxArea, tmpMaxArea)
                currIslandId++;
            }
        }
    }
 
    return currMaxArea
};
 
var maxAreaRecursive = function(grid, currIslandId, i, j) {
    if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length)
        return 0;
 
    if (grid[i][j] === 0 || grid[i][j] === currIslandId) return 0;
 
    grid[i][j] = currIslandId;
 
    return 1 + 
        maxAreaRecursive(grid, currIslandId, i+1, j) + 
        maxAreaRecursive(grid, currIslandId, i-1, j) + 
        maxAreaRecursive(grid, currIslandId, i, j+1) + 
        maxAreaRecursive(grid, currIslandId, i, j-1);
}

Leave a Reply

Your email address will not be published. Required fields are marked *