Grow the Largest Island by Changing at Most One Cell
Company: TikTok
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
In the binary square grid, an island is a side-connected set of 1 cells. You may change at most one 0 to 1. Return the largest island size obtainable, allowing no change.
```cpp
class Solution {
public:
int largestIsland(vector<vector<int>>& grid);
};
```
### Examples
**Example 1:**
```text
grid = [[0,0],[0,0]]
Output: 1
Explanation: Changing any one cell creates a singleton island.
```
**Example 2:**
```text
grid = [[1,0,1],[1,0,1],[0,0,0]]
Output: 5
Explanation: Flip(0,1) to join the two size2 islands through one new cell. No flip can add more than those four existing land cells plus itself.
```
### Constraints
- Grid dimensions are n-by-n with 1 <= n <=500.
- Cells contain only 0 or 1.
### Contract considerations
Preserve the at-most-one operation and four-neighbor island definition.
```hint Read the boundary condition
Which distinct components can one new land cell join?
```
### Boundary reminders
Preserve the at-most-one operation and four-neighbor island definition.
Overview: Grow the Largest Island by Changing at Most One Cell. In the binary square grid, an island is a side-connected set of 1 cells.