Making A Large Island

Hard

You are given an n x n binary grid. You may change at most one 0 to a 1. Return the size of the largest island (a 4-directionally connected group of 1s) achievable after at most one such change.

Example 1

Input:  grid = [[1,0],[0,1]]
Output: 3

Example 2

Input:  grid = [[1,1],[1,0]]
Output: 4

Example 3

Input:  grid = [[1,1],[1,1]]
Output: 4

Constraints

• n == grid.length == grid[i].length
• 1 <= n <= 500
• grid[i][j] is 0 or 1.