Katkat
Back

Shortest Bridge to Connect Two Islands

TeslaSoftware Engineer · Onsite
EasySoftware EngineerOnsiteCoding & Algorithms

Last updated

Tests matrix traversal techniques, specifically using DFS/BFS to identify connected components and multi-source BFS to find the shortest path between them.

Shortest Bridge to Connect Two Islands

You are given an n x n binary matrix grid where 1 represents land and 0 represents water.

An island is a 4-directionally connected group of 1s not connected to any other 1s. There are exactly two distinct islands in grid.

You may change 0s to 1s to connect the two islands into a single connected component.

Return the minimum number of 0s that must be flipped to 1 to connect the two islands.

Function Signature

def shortest_bridge(grid: list[list[int]]) -> int:
    pass

Constraints

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

Examples

Example 1:

Input: grid = [
  [0, 1],
  [1, 0]
]
Output: 1
Explanation: Flipping grid[0][0] or grid[1][1] from 0 to 1 connects the two islands.

Example 2:

Input: grid = [
  [0, 1, 0],
  [0, 0, 0],
  [0, 0, 1]
]
Output: 2
Explanation: We can flip grid[0][2] and grid[1][2] to connect the two islands.

Example 3:

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

Edge Cases to Consider

  • Islands that are separated by only a single layer of water (output = 1).
  • Islands located at opposite corners of a large grid.
  • One island forming a concave or enclosing shape around the other without touching.

Hints

Hint 1

Locate the first island using a standard DFS or BFS traversal and mark all its cells so you can distinguish it from the second island.

Hint 2

Initialize a queue with all cells belonging to the first island to perform a multi-source Breadth-First Search (BFS).

Hint 3

Expand outward level-by-level across water cells (0s); the first time your expansion reaches a cell of the second island, the current level count is your answer.

Follow-up questions

  • How would you implement bidirectional BFS to reduce the search space on larger grids?
  • How would your approach change if diagonal movements (8-directional connectivity) were permitted?
  • If the grid had k islands instead of two and you needed to connect all of them with the minimum number of flips, what algorithm would you use?