Intuition
- Same idea as Number of Islands, but you count via DFS instead via a starting point
Complexity
Runtime
since you touch every row,col once, and a set is seen to have constant access time.
Space
since you can store at most MN items in the axillary set.
Code
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
def adj(r, c):
res = []
for i, j in [(r + 1, c), (r - 1, c), (r, c - 1), (r, c + 1)]:
if 0 <= i < m and 0 <= j < n:
res.append((i, j))
return res
seen = set()
def dfs(r, c):
if grid[r][c] == 0:
return 0
cur_area = 1
more_island = False
seen.add((r, c))
for i, j in adj(r, c):
if grid[i][j] == 1 and (i, j) not in seen:
cur_area += dfs(i, j)
return cur_area
max_area = 0
for r in range(m):
for c in range(n):
if grid[r][c] == 1 and (r, c) not in seen:
max_area = max(max_area, dfs(r, c))
return max_area