The challenge

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 ``.

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 `` or 1.

The solution in Python code

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        def get_neighbor(pos,grid):
            y,x = pos
            ns = []
            if x>=1:
                ns.append((y,x-1))
            if x<len(grid[0])-1:
                ns.append((y,x+1))
            if y>=1:
                ns.append((y-1,x))
            if y<len(grid)-1:
                ns.append((y+1,x))

            return ns
        marked = set()
        land = []

        for row in range(len(grid)):
            for col in range(len(grid[row])):
                if grid[row][col] == 1 and (row,col) not in marked:
                    curr_land_len = 1
                    marked.add((row,col))
                    stack = [(row,col)]

                    while stack:
                        current = stack.pop()
                        neighbor = get_neighbor(current,grid)
                        for n in neighbor:
                            y,x = n
                            if grid[y][x] == 1 and (y,x) not in marked:
                                marked.add((y,x))
                                curr_land_len += 1
                                stack.append((y,x))

                    land.append(curr_land_len)

        return (max(land) if len(land)!=0 else 0)