Making a Large Island

Given an n × n binary grid, change at most one zero to one. Land cells connect only through shared sides. Return the largest island area obtainable, counting…

Given an n × n binary grid, change at most one zero to one. Land cells connect only through shared sides. Return the largest island area obtainable, counting cells, including the option to make no change.

1 <= n <= 500; cells are integers 0 or 1. Brute force is a small-input baseline and does not meet the maximum constraint. Visual presets are limited to 4×4 for brute force and 6×6 for DSU.

Example 1: input grid = [[0,0],[0,0]]; output 1. The grid has no land. Flipping one zero creates a single-cell island, so the maximum area is one.

Example 2: input grid = [[1,1,0],[1,1,0],[0,0,0]]; output 5. Flipping (0, 2) connects the new cell to the existing four-cell island. The largest area becomes five.

Category: Graphs. Topic: graph. Difficulty: Hard. Patterns: graph-traversal.