Practice/Meta/Leetcode 934. Shortest Bridge

Leetcode 934. Shortest Bridge

CodingMust

Problem

You are given an n × n binary matrix where each cell contains either 0 (water) or 1 (land). The matrix contains exactly two separate islands, where an island is defined as a group of 1s connected horizontally or vertically (4-directional connectivity).

Your task is to find the minimum number of water cells (0s) that need to be changed to land cells (1s) to connect the two islands together.

Requirements

1. Identify both islands in the grid
2. Calculate the shortest path between the boundaries of the two islands
3. Return the minimum number of cell flips needed to bridge them
4. The bridge must use 4-directional connectivity (horizontal and vertical only)

Constraints

• 2 ≤ n ≤ 100
• grid.length == n
• grid[i].length == n
• grid[i][j] is either 0 or 1
• There are exactly two islands in the grid
• Time complexity should be O(n²)
• Space complexity should be O(n²)

Examples

Example 1:

Input: grid = [[0,1],[1,0]] Output: 1 Explanation: We have two single-cell islands at positions (0,1) and (1,0). We need to flip 1 cell to connect them (either cell (0,0) or (1,1)).

Example 2:

Input: grid = [[1,1,1,1,1], [1,0,0,0,1], [1,0,1,0,1], [1,0,0,0,1], [1,1,1,1,1]] Output: 1 Explanation: The outer border forms one island, the center cell is another. Only one flip of any adjacent water cell connects them.

Example 3:

Input: grid = [[1,1,0,0,0], [1,0,0,0,0], [0,0,0,0,1], [0,0,0,1,1], [0,0,0,0,0]] Output: 2 Explanation: The top-left island and bottom-right island require flipping 2 cells to create the shortest bridge.