Shortest Bridge

CodingPhoneSoftware EngineerReported September 2025

You receive a binary grid with precisely two islands; cells containing 1 represent land, and cells containing 0 represent water.

Find the smallest number of 0 cells that need to be changed into 1s so that the islands become connected.

Examples

Example 1:

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

Output: 1

Example 2:

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

Output: 2

Constraints

• 2 <= grid.length == grid[i].length <= 100
• The grid contains exactly two islands.

Company Notes

This was reported as LeetCode 934 during a software engineer phone screen.