695. Max Area of Island
Given a 2D grid of 0s and 1s, find the maximum area of an island.
Approach: DFS
When we encounter a cell with value 1 (land), we perform a depth-first search (DFS) to explore all connected land cells and calculate the area of the island and update the maximum area found so far.
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
ans = 0
def dfs(r, c):
if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] == 0:
return 0
grid[r][c] = 0
return (1 + dfs(r-1, c) + dfs(r+1, c) +
dfs(r, c-1) + dfs(r, c+1))
for i in range(rows):
for j in range(cols):
if grid[i][j] == 1:
ans = max(ans, dfs(i, j))
return ans- Time: — we visit each cell at most once.
- Space: — in the worst case, the recursion stack can go as deep as the number of cells in the grid (all land cells).
Last updated on