[leetCode] 695. Max Area of Island

Description

You are given an m x n binary matrix grid. An island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

Example 1:

Input: grid = [
[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]
]

Output: 6
Explanation: The answer is not 11, because the island must be connected 4-directionally.

Example 2:

Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0

Solution

var maxAreaOfIsland = function(grid) {
   if (grid.length == 0) return 0;
   let height = grid.length, width = grid[0].length;
   let max = 0;
   for (let row = 0; row < height; row++) {
       for (let col = 0; col < width; col++) {
           if (grid[row][col] == 1) {
               max = Math.max(max, dfs(row, col, grid));
           }
       }
   }
   
   return max;    
};

function dfs(r, c, grid) {
   if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length 
       || grid[r][c] === 0) return 0;
   const DIRECTIONS = [[-1,0], [0,1], [1,0], [0,-1]];
   let count = 1;
   grid[r][c] = 0;
   for (let dir of DIRECTIONS) {
       count += dfs(r + dir[0], c + dir[1], grid);
   }
   return count;
}