Narrowest Bridge

MediumGraphs

Problem

A map grid (1 land, 0 water) contains exactly two islands, each a group of land cells connected horizontally or vertically.

Engineers want to join them by filling water cells with earth, so that the two islands become one 4-connected island. Return the minimum number of water cells that must be filled.

Example 1

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

Filling either (0,0) or (1,1) connects the two cells.

Example 2

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

Example 3

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

Any shortest bridge between opposite corners crosses three water cells, e.g. (0,1), (0,2), (1,2).

Constraints

  • 2 ≤ rows · cols
  • 1 ≤ rows, cols ≤ 200
  • grid[r][c] is 0 or 1
  • There are exactly two islands.

Hint

Show the first hint

The answer is a distance: from one whole island to the other.

Walkthrough

How to approach it

01Clarify before coding

  • Are there always exactly two islands? Yes.
  • Does the bridge have to be 4-connected? Yes, diagonal contact does not join islands.
  • Do I return the number of filled cells or the path? The count.

02Brute force

For every land cell of island A and every land cell of island B, compute the Manhattan distance minus 1 and take the minimum.

Cost: O(|A| · |B|), up to about 10^9 pairs on a 200 × 200 map. (It is correct here because there are no obstacles, but too slow.)

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.