Make the largest island
A square grid grid has n rows and n columns. Each cell is 1 (land) or 0 (water). An island is a group of land cells joined through shared sides: up, down, left or right. Cells that touch only at a corner are not joined.
You may turn at most one water cell into land. Return the size, in cells, of the largest island the grid can have after that. If the grid has no water, there is nothing to change, so the answer is n × n. You may change grid while you work.
Cells are written (row, column), counting from 0.
grid = [[1, 1, 0, 0], [1, 0, 1, 1], [0, 1, 0, 0], [0, 1, 0, 1]]Output8Turn (1, 1) into land. It joins the island of 3 at the top left, the island of 2 to its right and the island of 2 below it: 1 + 3 + 2 + 2 = 8.
grid = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]Output9The middle cell touches the same ring of 8 on all four sides. The ring counts once: 8 + 1 = 9.
grid = [[0, 0], [0, 0]]Output1All water. One new land cell is an island of size 1.
1 ≤ n ≤ 500
gridhas n rows of n cells, each 0 or 1.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.