# LeetCode 695: Max Area of Island

## Problem Restatement

We are given an `m x n` binary matrix `grid`.

| Value | Meaning |
|---|---|
| `1` | Land |
| `0` | Water |

An island is a group of land cells connected horizontally or vertically.

The area of an island is the number of cells in that connected component.

We need to return the maximum island area in the grid.

If there is no island, return `0`. The official statement defines islands using 4-directional adjacency and asks for the largest connected land area. ([leetcode.com](https://leetcode.com/problems/max-area-of-island/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | Binary matrix `grid` |
| Output | Maximum island area |
| Connectivity | Up, down, left, right |
| Area | Number of land cells |

Example function shape:

```python
def maxAreaOfIsland(grid: list[list[int]]) -> int:
    ...
```

## Examples

Example 1:

```python
grid = [
    [0,0,1,0,0],
    [1,1,1,0,0],
    [0,0,0,1,1],
    [0,1,0,1,1],
]
```

There are multiple islands.

The island:

```text
(0,2)
(1,0)
(1,1)
(1,2)
```

is connected and has area:

```text
4
```

The bottom-right island also has area `4`.

Answer:

```python
4
```

Example 2:

```python
grid = [
    [0,0,0],
    [0,0,0],
]
```

There is no land.

Answer:

```python
0
```

## First Thought: Count Each Island

This is similar to the standard number of islands problem.

When we find a land cell:

```text
grid[r][c] == 1
```

we can run DFS or BFS to traverse the entire island.

But instead of just counting islands, we count how many land cells belong to the current island.

The largest count is the answer.

## Key Insight

DFS naturally computes connected component size.

Suppose DFS visits one land cell.

Then:

1. Count the current cell as area `1`.
2. Visit all connected neighbors.
3. Add their areas recursively.

So the DFS return value can be:

```text
Area of the island connected to this cell
```

## Algorithm

1. Initialize:
   ```python id="jlwmr5"
   best = 0
   ```
2. Scan every cell in the grid.
3. When land `1` is found:
   - Run DFS.
   - DFS returns the island area.
   - Update `best`.
4. Return `best`.

DFS steps:

1. If outside the grid or on water, return `0`.
2. Mark the current land cell as visited.
3. Return:
   ```python
   1 + dfs(up) + dfs(down) + dfs(left) + dfs(right)
   ```

We mark visited cells by changing them from `1` to `0`.

## Walkthrough

Consider:

```python
grid = [
    [0,0,1,0,0],
    [1,1,1,0,0],
    [0,0,0,1,1],
    [0,1,0,1,1],
]
```

Start scanning.

At `(0,2)` we find land.

DFS explores:

```text
(0,2)
(1,2)
(1,1)
(1,0)
```

Area:

```text
4
```

Update:

```python
best = 4
```

Continue scanning.

Later, another island also has area `4`.

The maximum remains:

```python
4
```

Return:

```python
4
```

## Correctness

The DFS starts from an unvisited land cell.

It visits the current cell and recursively visits every horizontally or vertically connected land neighbor.

Because recursion continues through all connected land cells, DFS visits exactly the cells belonging to that island.

Each visited land cell contributes exactly `1` to the total area.

Visited cells are marked as water, so no cell is counted more than once.

Therefore, the DFS return value equals the area of the connected island containing the starting cell.

The outer scan starts DFS once for every island and updates the maximum area seen.

Thus, the algorithm returns the largest island area in the grid.

## Complexity

Let:

| Symbol | Meaning |
|---|---|
| `m` | Number of rows |
| `n` | Number of columns |

| Metric | Value | Why |
|---|---:|---|
| Time | `O(m * n)` | Every cell is visited at most once |
| Space | `O(m * n)` worst case | Recursion stack in a fully connected island |

For a sparse grid, recursion depth is smaller.

## Implementation

```python
class Solution:
    def maxAreaOfIsland(self, grid: list[list[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])

        def dfs(r: int, c: int) -> int:
            if r < 0 or r >= rows or c < 0 or c >= cols:
                return 0

            if 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)
            )

        best = 0

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    best = max(best, dfs(r, c))

        return best
```

## Code Explanation

The helper:

```python
def dfs(r: int, c: int) -> int:
```

returns the area of the island connected to `(r, c)`.

If the cell is invalid or water:

```python
if grid[r][c] == 0:
    return 0
```

there is no area contribution.

When we visit land:

```python
grid[r][c] = 0
```

we mark it visited.

Then we count:

| Part | Meaning |
|---|---|
| `1` | Current cell |
| `dfs(...)` | Neighbor island area |

So:

```python
return (
    1
    + dfs(r + 1, c)
    + dfs(r - 1, c)
    + dfs(r, c + 1)
    + dfs(r, c - 1)
)
```

computes the full connected component size.

The outer loops scan the whole grid:

```python
for r in range(rows):
    for c in range(cols):
```

Whenever new land is found:

```python
if grid[r][c] == 1:
```

we compute that island's area and update the maximum.

## BFS Version

The same problem can also be solved with BFS.

```python
from collections import deque

class Solution:
    def maxAreaOfIsland(self, grid: list[list[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])

        best = 0

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] != 1:
                    continue

                queue = deque([(r, c)])
                grid[r][c] = 0
                area = 0

                while queue:
                    cr, cc = queue.popleft()
                    area += 1

                    for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
                        nr = cr + dr
                        nc = cc + dc

                        if (
                            0 <= nr < rows
                            and 0 <= nc < cols
                            and grid[nr][nc] == 1
                        ):
                            grid[nr][nc] = 0
                            queue.append((nr, nc))

                best = max(best, area)

        return best
```

## Testing

```python
def run_tests():
    s = Solution()

    grid = [
        [0,0,1,0,0],
        [1,1,1,0,0],
        [0,0,0,1,1],
        [0,1,0,1,1],
    ]
    assert s.maxAreaOfIsland(grid) == 4

    grid = [
        [0,0,0],
        [0,0,0],
    ]
    assert s.maxAreaOfIsland(grid) == 0

    grid = [
        [1],
    ]
    assert s.maxAreaOfIsland(grid) == 1

    grid = [
        [1,1],
        [1,1],
    ]
    assert s.maxAreaOfIsland(grid) == 4

    grid = [
        [1,0,1,0,1],
    ]
    assert s.maxAreaOfIsland(grid) == 1

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Expected | Why |
|---|---:|---|
| Mixed grid | `4` | Largest connected component size |
| All water | `0` | No islands |
| Single land cell | `1` | Smallest island |
| Fully connected `2 x 2` island | `4` | Entire grid connected |
| Separate single-cell islands | `1` | No horizontal connection |