Problem Statement

Given a 2D binary matrix of size n x n, return the integer representing the size of the largest island after changing at most 0 to 1.

Here, Island is defined as a 4-directionally connected group of 1s.

Examples

• Example 1:

  • Input:

    [[1, 0, 1, 0],
     [0, 1, 1, 0],
     [0, 0, 0, 1],
     [1, 1, 0, 0]]
    

  • Expected Output: 6
  • Justification: Converting the water cell at position (2,1) will connect two large islands (top right and bottom left) with a new land cell, creating an island of size 6.

• Example 2:

  • Input:

    [[1, 1, 1],
     [1, 0, 0],
     [0, 0, 1]]
    

  • Expected Output: 6
  • Justification: Changing the cell (1,2) into land will connect the top horizontal island with the bottom right cell, resulting in a single island of size 6.

• Example 3:

  • Input:

    [[0, 1, 0],
     [1, 0, 1],
     [0, 1, 0]]
    

  • Expected Output: 5
  • Justification: By converting the center cell (1,1) to land, all surrounding cells will connect, forming a cross-shaped island with 5 cells.

Constraints:

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

Try it yourself

Try solving this question here: