Core Insight A visited structure makes each vertex’s work happen at most once.
Common Pitfall Mark a node visited when it is scheduled, not after duplicate work is queued.
Description
Find the maximum area of an island.
Constraints
- Time Complexity:
O(m·n) - Space Complexity:
O(m·n)
Tags
arraydfsbfsunion-findmatrix
Implementation Plan Translate the invariant into these small, testable moves.
- Choose a start node or component.
- Add it to the traversal frontier.
- Visit valid unseen neighbors.
- Repeat for every remaining component if needed.
def maxAreaOfIsland(grid):
ROWS, COLS = len(grid), len(grid[0])
visit = set()
def dfs(r, c):
if (r < 0 or r == ROWS or c < 0 or c == COLS or
grid[r][c] == 0 or (r, c) in visit):
return 0
visit.add((r, c))
return (1 + dfs(r + 1, c) + dfs(r - 1, c) +
dfs(r, c + 1) + dfs(r, c - 1))
area = 0
for r in range(ROWS):
for c in range(COLS):
area = max(area, dfs(r, c))
return area