# LeetCode 827: Making A Large Island

## Problem Restatement

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

Each cell is either:

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

An island is a group of land cells connected in four directions:

```python
up, down, left, right
```

We may change at most one `0` into `1`.

Return the largest possible island size after doing this operation.

If the grid is already all land, we return the size of the whole grid.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A square binary matrix `grid` |
| Output | The maximum possible island size |
| Operation | Change at most one `0` to `1` |
| Connectivity | Four-directional only |
| Constraint | `1 <= n <= 500` |

Function shape:

```python
class Solution:
    def largestIsland(self, grid: list[list[int]]) -> int:
        ...
```

## Examples

Example 1:

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

There are two separate islands, each with size `1`.

If we flip the top-right `0`, the grid becomes:

```python
[
    [1, 1],
    [0, 1],
]
```

Now the island has size `3`.

So the answer is:

```python
3
```

Example 2:

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

There is already one island of size `3`.

If we flip the only `0`, the full grid becomes land.

So the answer is:

```python
4
```

Example 3:

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

There is no `0` to flip.

The largest island is already the whole grid.

So the answer is:

```python
4
```

## First Thought: Brute Force

A direct approach is:

1. Try every `0` cell.
2. Temporarily change it to `1`.
3. Run DFS or BFS to find the largest island.
4. Restore the cell back to `0`.

This works, but it repeats a lot of work.

Code sketch:

```python
class Solution:
    def largestIsland(self, grid: list[list[int]]) -> int:
        n = len(grid)
        answer = 0

        def dfs(r: int, c: int, seen: set[tuple[int, int]]) -> int:
            if r < 0 or r >= n or c < 0 or c >= n:
                return 0
            if grid[r][c] == 0 or (r, c) in seen:
                return 0

            seen.add((r, c))
            return (
                1
                + dfs(r + 1, c, seen)
                + dfs(r - 1, c, seen)
                + dfs(r, c + 1, seen)
                + dfs(r, c - 1, seen)
            )

        for r in range(n):
            for c in range(n):
                if grid[r][c] == 0:
                    grid[r][c] = 1

                    seen = set()
                    best = 0

                    for i in range(n):
                        for j in range(n):
                            if grid[i][j] == 1 and (i, j) not in seen:
                                best = max(best, dfs(i, j, seen))

                    answer = max(answer, best)
                    grid[r][c] = 0

        return answer if answer > 0 else n * n
```

## Problem With Brute Force

There can be up to:

```python
n * n
```

cells.

For every `0`, the brute force approach may scan the whole grid again.

Since `n` can be as large as `500`, the grid may contain:

```python
500 * 500 = 250000
```

cells.

Repeating a full DFS for many zero cells is too slow.

We need to compute island sizes once, then reuse them.

## Key Insight

Instead of recalculating islands after every possible flip, label every existing island first.

For each island, give it a unique id and record its size.

For example:

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

We can relabel it as:

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

Now:

```python
size[2] = 3
size[3] = 2
```

When checking a `0`, we only look at its four neighbors.

If those neighbors belong to islands `2` and `3`, flipping this `0` would create:

```python
1 + size[2] + size[3]
```

The `1` is the flipped cell itself.

We must be careful not to count the same island twice.

## Algorithm

Use two phases.

Phase 1: Label islands.

1. Start island ids from `2`.
2. Scan every cell.
3. When we find a `1`, run DFS from it.
4. Change every cell in that island from `1` to the current island id.
5. Store the island size in a dictionary.

We start ids from `2` because:

| Value | Meaning |
|---|---|
| `0` | Water |
| `1` | Unvisited land |
| `2+` | Labeled island id |

Phase 2: Try flipping each `0`.

For each `0` cell:

1. Look at its four neighbors.
2. Collect distinct island ids.
3. Sum their sizes.
4. Add `1` for the flipped cell.
5. Update the answer.

If there is no `0`, the answer is `n * n`.

## Walkthrough

Use:

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

First, label islands.

The top-left island gets id `2`:

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

Its size is:

```python
size[2] = 1
```

The bottom-right island gets id `3`:

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

Its size is:

```python
size[3] = 1
```

Now try each `0`.

At cell `(0, 1)`, its neighboring islands are `2` and `3`.

So flipping it gives:

```python
1 + size[2] + size[3] = 3
```

At cell `(1, 0)`, the same result is possible.

So the answer is:

```python
3
```

## Correctness

After phase 1, every original island has exactly one unique id.

The DFS visits all land cells connected to the starting cell and assigns the same id to all of them. It does not visit water cells, and it does not cross island boundaries. Therefore, each recorded size is exactly the number of cells in that island.

Now consider any `0` cell. If we flip it to `1`, it can only connect islands adjacent to it in the four directions. It cannot connect to islands farther away without a direct path through land.

So the new island formed by flipping this cell has size equal to:

```python
1 + sum(size[id] for each distinct neighboring island id)
```

The distinct-id set prevents counting the same island multiple times when the flipped cell touches the same island from more than one side.

The algorithm checks every possible `0` cell, computes the exact island size produced by flipping it, and takes the maximum. If there is no `0`, no flip is possible, and the whole grid is already one island of size `n * n`.

Therefore, the algorithm returns the largest possible island size.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n^2)` | Each cell is labeled once, then each cell is checked once |
| Space | `O(n^2)` | The island size map and DFS stack can grow with the grid size |

The grid is modified in place, so we do not need a separate visited matrix.

## Implementation

```python
class Solution:
    def largestIsland(self, grid: list[list[int]]) -> int:
        n = len(grid)
        sizes = {}
        island_id = 2

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        def dfs(r: int, c: int, island_id: int) -> int:
            if r < 0 or r >= n or c < 0 or c >= n:
                return 0
            if grid[r][c] != 1:
                return 0

            grid[r][c] = island_id
            area = 1

            for dr, dc in directions:
                area += dfs(r + dr, c + dc, island_id)

            return area

        for r in range(n):
            for c in range(n):
                if grid[r][c] == 1:
                    sizes[island_id] = dfs(r, c, island_id)
                    island_id += 1

        answer = max(sizes.values(), default=0)

        for r in range(n):
            for c in range(n):
                if grid[r][c] == 0:
                    seen = set()

                    for dr, dc in directions:
                        nr = r + dr
                        nc = c + dc

                        if 0 <= nr < n and 0 <= nc < n:
                            neighbor_id = grid[nr][nc]
                            if neighbor_id > 1:
                                seen.add(neighbor_id)

                    area = 1
                    for neighbor_id in seen:
                        area += sizes[neighbor_id]

                    answer = max(answer, area)

        return answer
```

## Code Explanation

We store each island's size here:

```python
sizes = {}
```

The first island id is `2`:

```python
island_id = 2
```

This avoids conflict with `0` and `1`.

The DFS labels one full island:

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

If the cell is outside the grid or not unvisited land, it contributes `0`:

```python
if r < 0 or r >= n or c < 0 or c >= n:
    return 0
if grid[r][c] != 1:
    return 0
```

Otherwise, we mark it with the island id:

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

Then we count it and continue in four directions.

After all islands are labeled, we start with the largest existing island:

```python
answer = max(sizes.values(), default=0)
```

This handles cases where the best move is effectively no move, such as an all-land grid.

Then for each water cell, we collect neighboring island ids:

```python
seen = set()
```

The set matters because one island can touch the same `0` from multiple sides.

For example:

```python
[
    [1, 1],
    [1, 0],
]
```

The `0` touches the same island from above and left. We should add that island size only once.

Finally, we compute:

```python
area = 1
for neighbor_id in seen:
    area += sizes[neighbor_id]
```

and update the answer.

## Testing

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

    assert s.largestIsland([
        [1, 0],
        [0, 1],
    ]) == 3

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

    assert s.largestIsland([
        [1, 1],
        [1, 1],
    ]) == 4

    assert s.largestIsland([
        [0, 0],
        [0, 0],
    ]) == 1

    assert s.largestIsland([
        [1, 1, 0],
        [1, 0, 0],
        [0, 1, 1],
    ]) == 6

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Diagonal islands | Confirms diagonal cells are not connected unless a flip connects them |
| One missing cell | Confirms flipping can complete the full grid |
| All land | Confirms no flip is required |
| All water | Confirms one flip creates size `1` |
| Multiple neighboring islands | Confirms distinct island ids are merged correctly |