Shortest Bridge
Medium · Graphs · Array · Depth-First Search · Breadth-First Search · Matrix
Problem
You are given an n x n grid where 1 is land and 0 is water. An island is a group of land cells joined up, down, left or right, and the grid holds exactly two islands.
You may turn water cells into land. Return the fewest water cells you must turn into land so that the two islands join into one.
Examples
Input: grid = [[1,0,0],[0,0,0],[0,0,1]] Output: 3
The corners are 4 steps apart, so the 3 water cells in between must become land.
Input: grid = [[0,1],[1,0]] Output: 1
The two cells touch only at a corner: one flip joins them.
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
The center cell is one water cell away from the ring.
Constraints
- n == len(grid) == len(grid[i])
- 2 <= n <= 100
- grid[i][j] is 0 or 1
- grid holds exactly two islands
Approaches
- Baseline: closest pair of cells — time O(n⁴), space O(n²)
Follow-up
What if the grid had many islands and you wanted the cheapest bridge between any two of them? Label every island, then grow all of them at once; the first time two different labels meet gives the answer. That is the first use case below.
Related problems
Start free on Cariara · Coding problems · System design studio
