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); } |