Build the Biggest Island With One Extra Cell
Implement biggestIsland
You are given a map of land (1) and water (0). You may turn at most one water cell into land. What is the size of the largest island you can get?
Turning a water cell into land merges every island that touches it. If the islands are labelled and their sizes are known in advance, the result for one water cell is 1 plus the sizes of the different neighbouring islands, so no repeated flood fills are needed.
Example 1:
Input: grid = [[1,0,0,1],[1,0,1,1],[0,0,0,0],[1,1,0,1]]
Output: 6
Example 2:
Input: grid = [[1,1],[1,1]]
Output: 4
Example 3:
Input: grid = [[0,0],[0,0]]
Output: 1
+ 13 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ rows, cols ≤ 8; grid[r][c] is 1 (land) or 0 (water) - ●
An island is a group of land cells connected through shared sides (up, down, left, right) - ●
You may change at most one water cell into land - ●
Return the size (number of cells) of the largest island that can be obtained
grid =
[[1,0,0,1], [1,0,1,1], [0,0,0,0], [1,1,0,1]]