Problem Statement

You are given a square grid (n x n) made up of 1s (land) and 0s (water). There are exactly two separate islands in the grid.

An island is defined as a group of connected 1s that are not connected to any other 1s.

Return the minimum number of 0s that need to be flipped to connect the two islands into one if you can change any 0 to 1 to connect the two islands.

Examples

Example 1:

• Input: grid =

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

• Expected Output: 2
• Explanation: Changing the zeros at (1,1) and (1,2) will connect the two islands. Also, changing the zeros at (1,1) and (2,1) will connect the two islands.

Example 2:

• Input: grid =

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

• Expected Output: 2
• Explanation: Changing the zeros at (1,4) and (2,4) or (2, 3) and (2, 4) will connect the two islands.

Example 3:

• Input: grid =

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

• Expected Output: 1
• Explanation: Changing the zero at (1,2) will connect the two islands.

Constraints:

• n == grid.length == grid[i].length
• 2 <= n <= 100
• grid[i][j] is either 0 or 1.
• There are exactly two islands in grid.

Try it yourself

Try solving this question here: