LeetMotion
You are given a binary matrix grid where grid[i][j] is 0 (water) or 1 (land). An island is a group of 1s connected horizontally or vertically. Return the maximum area of any island. If none exists, return 0.
1 ≤ grid.length, grid[i].length ≤ 50grid[i][j] is 0 or 1Both give the same O(m·n) answer, but BFS processes tiles in "waves" which makes the spreading behaviour visually intuitive — and naturally avoids the call-stack overflow risk that deep DFS can hit on very large grids. BFS also maps cleanly to the Rotting Oranges multi-source pattern you'll encounter next.
| Approach | Time | Space | Notes |
|---|---|---|---|
| DFS (recursive) | O(m·n) | O(m·n) | Call stack depth up to m·n |
| BFS (queue) | O(m·n) | O(min(m,n)) | No stack overflow risk ✓ |
🟧 Amber = land · 🟦 Indigo = queued · 🟠 Orange = being processed · 🟢 Green = visited
DFS explores each island recursively, going as deep as possible before backtracking. Identical time complexity to BFS — the choice is stylistic or stack-safety driven.
def maxAreaOfIsland(self, 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 areaIn BFS, mark the cell as visited (set to 0 or add to visited set) when you enqueue it, not when you dequeue it. If you wait until dequeue, the same cell can be added to the queue multiple times from different neighbors, inflating the area count.
Always check nr >= 0 and nr < ROWS and nc >= 0 and nc < COLS before checking grid[nr][nc]. Short-circuit evaluation prevents the out-of-bounds array access.
The BFS solution above marks cells by setting them to 0. If the problem requires the original grid to be preserved, either use a separate visited set or clone the grid before running the algorithm.
Discussion
…