Medium

Max Area of Island

027

Given a 0/1 grid, return the largest connected island area using four-directional adjacency.

EXAMPLES

Example 1

Input
{
  "grid": [
    [
      0,
      1,
      0
    ],
    [
      1,
      1,
      0
    ],
    [
      0,
      0,
      1
    ]
  ]
}

Output
3

FUNCTION SHAPE

grid: intMatrix→int

SOLUTION NOTE

Almost exact same problem as above, except we want the size of the island instead of sum of values in the island.

Reveal reference solution +

pythonREFERENCE

def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
    m,n,res = len(grid), len(grid[0]), 0
    dirs = [(0,1),(0,-1),(1,0),(-1,0)]
    def dfs(i,j):
        if not (0 <= i < m and 0 <= j < n) or grid[i][j] == 0: return 0
        grid[i][j] = 0
        return 1 + sum(dfs(i+x,j+y) for x,y in dirs)

    return max(dfs(i,j) for i in range(m) for j in range(n))

TimeO(m*n)

SpaceO(m*n)

Open on LeetCode ↗