514. Making A Large Island
Your function receives an n × n binary grid grid, where 1 is land and 0 is water. An island is a maximal group of land cells connected up/down/left/right (never diagonally).
You are allowed to convert at most one water cell into land. Return the size of the largest island the grid can contain after that single (optional) conversion.
If the grid is already all land, the answer is the whole grid, n * n. If it is all water, the best you can do is flip one cell for an island of size 1.
Example 1:
Input: grid = [[1, 0], [0, 1]]
Output: 3
Explanation: Flip either water cell: it touches both single-cell islands, joining them into one island of 1 + 1 + 1 = 3.
Example 2:
Input: grid = [[1, 1], [1, 0]]
Output: 4
Explanation: Flipping the lone water cell extends the 3-cell island to cover the whole grid.
Constraints:
- 1 ≤ n ≤ 500
- grid[r][c] is 0 or 1
Hints:
Brute force: try flipping each 0, then flood-fill to measure the island it lands in. That is O(n²) flips × O(n²) fill — fine to reason about, too slow at scale.
The flip only glues together islands that already exist. If every land cell knew which island it belongs to and how big that island is, a flipped 0 would be worth 1 + the sizes of the distinct islands touching its four sides.
Union-find (or a DFS labeling pass) gives you exactly that: group land cells into components with sizes, then evaluate every 0 in O(1). Deduplicate neighbor components by their root — an island touching the 0 on two sides must be counted once.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: grid = [[1, 0], [0, 1]]
Expected output: 3