Given an n x n grid of 0s and 1s, you may change at most one 0 to a 1. Return the size of the largest island (4-directionally connected 1s) you can obtain. If the grid is already all 1s, the answer is the whole grid.
Input: grid = [[1,0],[0,1]] Output: 3 Flipping a 0 joins the two size-1 islands into size 3.
Input: grid = [[1,1],[1,1]] Output: 4 Already one island of size 4; no flip needed.
- 1 <= n <= 500 - grid[i][j] is 0 or 1
Trying every flip and re-flooding is O((RC)²). The efficient idea precomputes island sizes once with union-find (each root stores its island's cell count), then evaluates each 0 in O(1) per neighbour:
For a candidate 0, look at its four neighbours, collect the distinct islands they belong to (by root — two neighbours might be the same island, so don't double-count), and sum their sizes plus 1 for the flipped cell. The best over all 0s (and the largest existing island, in case flipping helps nothing) is the answer. If there's no 0, the whole grid is one island of size RC.
“How many flips?”
At most one 0 to 1.
“What if there's no 0?”
The grid is already one island of size RC.
I union all land into islands with sizes, then for each 0 I sum its distinct neighbour islands plus one.
The max over all zeros (and the biggest existing island) is the answer.
Worked example — grid = [[1,0],[0,1]]
each 1 is its own island (size 1); flipping the center-adjacent 0 joins two size-1 islands + 1 = 3 answer = 3
Sum the sizes of the islands the 0 touches.
A 0 can border the same island twice.
Union-find makes each flip O(1) per neighbour.
| Flip-and-flood | Union-find sizes | |
|---|---|---|
| Idea | flip each 0, recount its island | sum distinct neighbour island sizes |
| Time | O((R·C)²) | O(R·C·α) |
| Reuse | recomputes per flip | sizes computed once |
Both give the same largest island; union-find avoids the repeated floods. Full code is in the Approaches selector below.
Key takeaway
Union land into islands with sizes; for each 0, sum its distinct neighbour islands' sizes + 1. The best (or RC if no 0) is the answer. O(R·C·α).
union islands with sizes for each 0: 1 + sum(size[root] for distinct neighbour roots) answer = max(best flip, largest existing island)
