Max Area of Island

Medium

Problem

In a binary grid, an island is a group of 1s connected up, down, left or right. Return the area (cell count) of the largest island, or 0 if there is none.

Example 1

Input:  [[0,0,1,0,0], [0,1,1,1,0], [0,0,1,0,0], [1,1,0,0,0]]
Output: 5

Test cases

Case 1

Input:    [[0,0,1,0,0],[0,1,1,1,0],[0,0,1,0,0],[1,1,0,0,0]]
Expected: 5

Case 2

Input:    [[0,0,0]]
Expected: 0

Case 3

Input:    [[1,1],[1,1]]
Expected: 4

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. DFS returning area

Time O(R·C)Space O(R·C) recursion worst case

Sink each land cell as you visit it and return 1 + the areas of its four neighbours.

function maxAreaOfIsland(grid) {
const R = grid.length, C = grid[0].length;
const area = (r, c) => {
if (r < 0 || c < 0 || r >= R || c >= C || grid[r][c] !== 1) return 0;
grid[r][c] = 0;
return 1 + area(r + 1, c) + area(r - 1, c) + area(r, c + 1) + area(r, c - 1);
};
let best = 0;
for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) best = Math.max(best, area(r, c));
return best;
}