Max Area of Island | Leetcode 695

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

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 50
• grid[i][j] is either 0 or 1.

Solution:

Idea is that once we find any land grid index value 1, we will mark that grid index visited and move with neighbors. Now as you can clearly see, It’s Depth First Search

class Solution {
   int[][] grid;
  
   public int maxAreaOfIsland(int[][] grid) {
      this.grid = grid;
      // in case of it's empty matrix we will return 0
      if (grid.length == 0)
         return 0;
     
      int ans = 0;
      //traversal of all the elements in the grid
      for (int r = 0; r < grid.length; r++) {
         for (int c = 0; c < grid[0].length; c++) {
            ans = Math.max(ans, area(r, c));
         }
      }
      return ans;
   }

   public int area(int r, int c) {
      // condition to skipping all invalid and processed blocks from matrix
      if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] == 0)
         return 0;
      // unset the bit
      grid[r][c] = 0;
     // recursively traversing till depth of Island with increament
      return 1 + area(r + 1, c) + area(r - 1, c) + area(r, c + 1) + area(r, c - 1);
   }
}

Complexity:

• Time complexity of the Max Area of Island solution would be O(R * C) where R is Row and C is column.
• Space complexity of the Max Area of Island solution would be O(1)