# Max Area of Island

- **Canonical ID**: `max-area-of-island`
- **Canonical URL**: https://dsacheatsheet.com/problems/max-area-of-island
- **Difficulty**: medium
- **Patterns**: Graphs
- **Version**: 1.0.0 (verified 2026-11-11T21:20:00Z)
- **Original Problem**: https://leetcode.com/problems/max-area-of-island/

## 1. Core Invariant / The Trick

DFS returns exact area contributed by a connected component (`1 + sum(4 neighbors)`), sinking `1 -> 0` upon arrival so each cell counts once.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(M * N)`
- **Space Complexity**: `O(M * N)`
- **Proof**: Every land cell flips to water once; DFS stack is bounded by total cells.

## 3. Minimal Idiomatic Code

### Python
```python
def maxAreaOfIsland(grid: list[list[int]]) -> int:
    R, C = len(grid), len(grid[0])
    def dfs(r: int, c: int) -> int:
        if not (0 <= r < R and 0 <= c < C and grid[r][c] == 1):
            return 0
        grid[r][c] = 0
        return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1)
    return max((dfs(r, c) for r in range(R) for c in range(C) if grid[r][c] == 1), default=0)
```

### TypeScript
```typescript
export function maxAreaOfIsland(grid: number[][]): number {
  const R = grid.length, C = grid[0].length;
  const dfs = (r: number, c: number): number => {
    if (r < 0 || r >= R || c < 0 || c >= C || grid[r][c] !== 1) return 0;
    grid[r][c] = 0;
    return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1);
  };
  let best = 0;
  for (let r = 0; r < R; r++) {
    for (let c = 0; c < C; c++) {
      if (grid[r][c] === 1) best = Math.max(best, dfs(r, c));
    }
  }
  return best;
}
```

### C++
```cpp
int maxAreaOfIsland(vector<vector<int>>& grid) {
    int R = grid.size(), C = grid[0].size(), best = 0;
    auto dfs = [&](auto& self, int r, int c) -> int {
        if (r < 0 || r >= R || c < 0 || c >= C || grid[r][c] != 1) return 0;
        grid[r][c] = 0;
        return 1 + self(self, r+1, c) + self(self, r-1, c) + self(self, r, c+1) + self(self, r, c-1);
    };
    for (int r = 0; r < R; ++r)
        for (int c = 0; c < C; ++c)
            if (grid[r][c] == 1) best = max(best, dfs(dfs, r, c));
    return best;
}
```

### Java
```java
int maxAreaOfIsland(int[][] grid) {
    int best = 0;
    for (int r = 0; r < grid.length; r++)
        for (int c = 0; c < grid[0].length; c++)
            if (grid[r][c] == 1) best = Math.max(best, dfs(grid, r, c));
    return best;
}
int dfs(int[][] g, int r, int c) {
    if (r < 0 || r >= g.length || c < 0 || c >= g[0].length || g[r][c] != 1) return 0;
    g[r][c] = 0;
    return 1 + dfs(g, r+1, c) + dfs(g, r-1, c) + dfs(g, r, c+1) + dfs(g, r, c-1);
}
```

### Go
```go
func maxAreaOfIsland(grid [][]int) int {
    R, C, best := len(grid), len(grid[0]), 0
    var dfs func(int, int) int
    dfs = func(r, c int) int {
        if r < 0 || r >= R || c < 0 || c >= C || grid[r][c] != 1 { 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 r := 0; r < R; r++ {
        for c := 0; c < C; c++ {
            if area := dfs(r, c); area > best { best = area }
        }
    }
    return best
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Forgetting all-water grids return `0` cleanly when `best = 0`.
- Mutating grid only if caller allows; otherwise keep a `visited` boolean matrix.

### Follow-ups
- Making a Large Island (flip one `0 -> 1`): label each island ID -> area, then probe each `0` cell summing unique neighbor island IDs + 1.