Max Area of Island

published on 4/29/2022

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 explanation:

First, we run dfs on the grid to find all the islands.
Then,for each island, we find the maximum area of each island.
And thne update the maxi with the maximum area for the island.
Finally, we return the maxi.

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        n,m,maxi = len(grid),len(grid[0]),0
        def dfs(i, j):
            if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or grid[i][j] != 1:
                return 0
            maxArea = 1
            grid[i][j] = '#'  # this will act as visited set
            maxArea += dfs(i+1, j)
            maxArea += dfs(i-1, j)
            maxArea += dfs(i, j+1)
            maxArea += dfs(i, j-1)
            return maxArea

        for i in range(n):
            for j in range(m):
                if grid[i][j] == 1:
                    maxi = max(dfs(i,j),maxi)
        return maxi