> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Making A Large Island Python Solution

> Tested Python solution for LeetCode 827 with 12 pytest cases. Generate a practice environment with lcpy.

LeetCode 827, [Hard](/catalog/hard). Topics: [Array](/catalog/topics/array), [Depth-First Search](/catalog/topics/depth-first-search), [Breadth-First Search](/catalog/topics/breadth-first-search), [Union-Find](/catalog/topics/union-find), [Matrix](/catalog/topics/matrix). [View on LeetCode](https://leetcode.com/problems/making-a-large-island/description/).

Generate this problem as a practice environment: tested reference solution, 12 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 827   # by problem number
lcpy gen -s making_a_large_island   # by problem name
```

## Problem

You are given an `n x n` binary matrix `grid`. You are allowed to change **at most one** `0` to be `1`.

Return *the size of the largest **island** in* `grid` *after applying this operation*.

An **island** is a 4-directionally connected group of `1`s.

### Examples

```
Input: grid = [[1,0],[0,1]]
Output: 3
Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3.
```

```
Input: grid = [[1,1],[1,0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.
```

```
Input: grid = [[1,1],[1,1]]
Output: 4
Explanation: Can't change any 0 to 1, only one island with area = 4.
```

### Constraints

* n == grid.length
* n == grid\[i].length
* 1 \<= n \<= 500
* grid\[i]\[j] is either 0 or 1.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/making_a_large_island/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/making_a_large_island/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(n^2)
    # Space: O(n^2)
    def largest_island(self, grid: list[list[int]]) -> int:
        n = len(grid)
        sizes = [0, 0]  # island ids start at 2 so 0/1 stay sentinel-free
        label = [[0] * n for _ in range(n)]

        for r in range(n):
            for c in range(n):
                if grid[r][c] == 0 or label[r][c]:
                    continue
                island_id = len(sizes)
                stack = [(r, c)]
                size = 0
                while stack:
                    x, y = stack.pop()
                    if not (0 <= x < n and 0 <= y < n) or grid[x][y] != 1 or label[x][y]:
                        continue
                    label[x][y] = island_id
                    size += 1
                    stack.extend(((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)))
                sizes.append(size)

        best = max(sizes)
        for r in range(n):
            for c in range(n):
                if grid[r][c] != 0:
                    continue
                nbr_ids = set()
                for x, y in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                    if 0 <= x < n and 0 <= y < n and grid[x][y] == 1:
                        nbr_ids.add(label[x][y])
                best = max(best, 1 + sum(sizes[i] for i in nbr_ids))
        return best
```

## Complexity

| Time | Space |
| - | - |
| O(n^2) | O(n^2) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.