Largest Island After Converting at Most One Water Cell to Land

You are given a rectangular grid in which `1` marks land and `0` marks water, and land cells connected horizontally or vertically form islands. You may change at most one water cell into land. Return the number of cells in the largest island the grid can contain after that change. In the interview, this followed the island-counting question. ### Function Signature ```python def largest_island_after_one_change(grid: list[list[int]]) -> int: ``` ### Rules - Two land cells are in the same island when a path of land cells joins them, each step moving one cell up, down, left or right; cells that touch only at a corner are not connected. - You may change one `0` to `1`, or change nothing. The answer is the largest island size over all of these choices. - The size of an island is its number of cells. If the grid has no water, the answer is the number of cells in the grid. - Coordinates in the examples are written `(row, column)`, counted from 0. ### Constraints - `1 <= len(grid) <= 500` and `1 <= len(grid[i]) <= 500`, with all rows the same length - every `grid[i][j]` is `0` or `1` - the answer is at most `250000` ### Examples **Example 1** ```text Input: grid = [[1, 0], [0, 1]] Output: 3 ``` Changing either water cell joins the two single-cell islands: 1 + 1 + 1 = 3. **Example 2** ```text Input: grid = [[1, 1], [1, 1]] Output: 4 ``` There is no water to change; the whole grid is already one island. **Example 3** ```text Input: grid = [[1, 1, 0, 0], [0, 0, 0, 1], [1, 0, 1, 1]] Output: 5 ``` Changing (2, 1) joins the single cell at (2, 0) and the three-cell island {(1, 3), (2, 2), (2, 3)}: 1 + 1 + 3 = 5. Changing (1, 2) touches that three-cell island on two sides but adds it only once, for a size of 4.