grid is a rectangle of 0s (water) and 1s (land). An island is a group of land cells joined horizontally or vertically, and its area is the number of cells in it. You may change at most one 0 into a 1.
Write largest_island(grid: list[list[int]]) -> int: the area of the biggest island you can end up with.
Examples:
grid = [[1, 1, 0, 0],
[1, 0, 0, 1],
[1, 1, 0, 1],
[0, 0, 1, 1]]
largest_island(grid) # 10
The grid has two islands: 5 cells on the left and 4 on the right. Filling [2, 2] (or [3, 1]) joins both and adds itself: 5 + 4 + 1 = 10. Filling [1, 1] only gives 6: it touches the left island three times, but that island still counts once.
largest_island([[1, 1], [1, 1]]) # 4 no water to fill, so the island stays as it is
largest_island([[0, 0], [0, 0]]) # 1 one filled cell on its own
Constraints: 1 <= rows, cols <= 500, and every cell is 0 or 1.
⭐ Bonus: speed tests on 500 × 500 grids earn a star in O(rows · cols). Trying each of the up to 250,000 water cells and measuring the islands again each time is billions of steps there.
Show hint
measure every island once, before trying any flips. Then a water cell's score is 1 plus the areas of the different islands among its four neighbours.