LeetCode 934: Shortest Bridge

Problem Restatement

We are given an n x n binary matrix grid.

Each cell is either:

0

or:

1

A 1 represents land.

A 0 represents water.

An island is a group of 1s connected in four directions:

up
down
left
right

The grid contains exactly two islands.

We may flip water cells from 0 to 1.

Return the smallest number of water cells we must flip to connect the two islands into one island. The official statement defines the grid this way and asks for the minimum number of 0s to flip.

Input and Output

Function shape:

class Solution:
    def shortestBridge(self, grid: list[list[int]]) -> int:
        ...

Examples

Example 1:

grid = [
    [0, 1],
    [1, 0],
]

There are two diagonal islands.

Diagonal cells are not connected, because only four-directional movement counts.

Flip one water cell:

[0, 1]      [1, 1]
[1, 0]  or  [1, 0]

The islands become connected.

Answer:

1

Example 2:

grid = [
    [0, 1, 0],
    [0, 0, 0],
    [0, 0, 1],
]

The shortest bridge needs two flips.

One path is:

(0, 1) -> (1, 1) -> (2, 1) -> (2, 2)

The water cells flipped are:

(1, 1), (2, 1)

Answer:

2

Example 3:

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],
]

The middle island is surrounded by water, and the outer ring is the other island.

Flip one adjacent water cell to connect them.

Answer:

1

These examples match the standard examples for this problem.

First Thought: Try Every Water Cell

One direct idea is to try flipping different sets of water cells until the islands connect.

But that quickly becomes too expensive.

There can be many water cells, and the number of possible sets is huge.

We need to view the problem as a shortest-distance problem on a grid.

Key Insight

We can solve the problem in two phases.

First, find one island and mark every cell in it.

Second, expand outward from all cells of that island at the same time using BFS.

The first time BFS reaches the second island, the current BFS distance is the minimum number of water cells we needed to flip.

This works because BFS explores cells in increasing distance order.

Since every water flip has the same cost, BFS gives the shortest bridge.

Algorithm

Use DFS to find and mark the first island.

While marking it, push all of its cells into a queue.

Then run multi-source BFS from that queue.

At each BFS layer:

1. Expand from all current cells.
2. If a neighbor is water, mark it visited and add it to the queue.
3. If a neighbor is land from the second island, return the current number of flips.

We can mark visited cells directly in grid by changing the first island and visited water cells to 2.

Walkthrough

Use:

grid = [
    [0, 1, 0],
    [0, 0, 0],
    [0, 0, 1],
]

First island:

(0, 1)

Mark it as 2 and put it in the queue.

Initial queue:

[(0, 1)]

Start BFS with:

flips = 0

Layer 0 expands from (0, 1).

It reaches water cells:

(0, 0), (0, 2), (1, 1)

These would require 1 flip.

Next layer:

flips = 1

Expand from those water cells.

From (1, 1), we can reach:

(2, 1)

That is another water cell.

Next layer:

flips = 2

Expand from (2, 1).

It touches the second island at:

(2, 2)

So the answer is:

2

Correctness

The DFS phase finds one land cell and marks every land cell connected to it by four-directional movement. Therefore, it marks exactly one of the two islands.

All cells of the first island are inserted into the BFS queue. So the BFS starts from every possible bridge starting point on that island, not just one cell.

During BFS, each layer corresponds to flipping one more water cell. Cells reached at distance d are exactly the water cells that can be connected to the first island by flipping d water cells.

BFS explores grid cells in increasing distance order. Therefore, the first time it touches a land cell that still has value 1, that land cell belongs to the second island, and the number of layers already expanded is the smallest possible number of water cells needed to connect the islands.

No shorter bridge can exist, because BFS would have reached the second island at an earlier layer.

So the returned value is the minimum number of flips.

Complexity

Let:

n = len(grid)

Implementation

from collections import deque

class Solution:
    def shortestBridge(self, grid: list[list[int]]) -> int:
        n = len(grid)
        queue = deque()
        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        def dfs(row: int, col: int) -> None:
            if row < 0 or row >= n or col < 0 or col >= n:
                return

            if grid[row][col] != 1:
                return

            grid[row][col] = 2
            queue.append((row, col))

            for dr, dc in dirs:
                dfs(row + dr, col + dc)

        found = False

        for row in range(n):
            if found:
                break

            for col in range(n):
                if grid[row][col] == 1:
                    dfs(row, col)
                    found = True
                    break

        flips = 0

        while queue:
            for _ in range(len(queue)):
                row, col = queue.popleft()

                for dr, dc in dirs:
                    nr = row + dr
                    nc = col + dc

                    if nr < 0 or nr >= n or nc < 0 or nc >= n:
                        continue

                    if grid[nr][nc] == 1:
                        return flips

                    if grid[nr][nc] == 0:
                        grid[nr][nc] = 2
                        queue.append((nr, nc))

            flips += 1

        return -1

Code Explanation

We use a queue for BFS:

queue = deque()

The four valid movement directions are:

dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]

The DFS marks the first island:

grid[row][col] = 2
queue.append((row, col))

Marking the cell as 2 means it has already been visited.

Adding it to the queue means BFS can later expand from every cell of the first island.

After the first island is marked, BFS begins:

flips = 0

For each BFS layer, we process the current queue size:

for _ in range(len(queue)):

If we reach a cell with value 1, it must belong to the second island:

if grid[nr][nc] == 1:
    return flips

If we reach water, we mark it and add it to the queue:

if grid[nr][nc] == 0:
    grid[nr][nc] = 2
    queue.append((nr, nc))

After each layer, we increase the number of flips:

flips += 1

Testing

def run_tests():
    s = Solution()

    assert s.shortestBridge([
        [0, 1],
        [1, 0],
    ]) == 1

    assert s.shortestBridge([
        [0, 1, 0],
        [0, 0, 0],
        [0, 0, 1],
    ]) == 2

    assert s.shortestBridge([
        [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],
    ]) == 1

    assert s.shortestBridge([
        [1, 0, 0],
        [0, 0, 0],
        [0, 0, 1],
    ]) == 3

    print("all tests passed")

run_tests()