Problem Statement

Shortest Bridge

You get an n x n grid filled with 0s and 1s. The 1s form exactly two islands. An island is a clump of 1s that touch each other up, down, left, or right. Your job is to build a bridge between the two islands by flipping some 0s into land, and you want to flip as few 0s as possible. Return that smallest number. The plan: first find one island and mark it, then spread outward from that island, one ring at a time, until you bump into the other island. The number of rings you spread is the bridge length.

mediumGraphBFSDFSGraphsTime: O(n^2) · Space: O(n^2)

Signals to notice

connect two islandsfind shortest bridgemulti-source BFS from one island

Brute force first

For each cell of island 1, BFS to each cell of island 2, take minimum. That instinct is useful because it follows the prompt literally, but it usually keeps revisiting work the problem is begging you to organize.

The key insight

DFS to find one island and mark all its cells. Then BFS from all cells of that island simultaneously. The first time BFS reaches a cell of the other island is the shortest bridge. Once you hold onto the right piece of information from moment to moment, the problem feels less like trial and error and more like following a shape that was there all along.

Trace it on `grid=[[0,1],[1,0]] (n=2)`

Scan grid: first 1 found at (0,1) -> run DFS to mark island 1
DFS: grid[0][1]=2, queue=[(0,1)]; all 4 neighbors are 0/out-of-bounds, so island 1 = {(0,1)}
BFS start steps=0. Process (0,1): (0,0)=0 -> mark 2 + enqueue; (1,1)=0 -> mark 2 + enqueue. queue=[(0,0),(1,1)]
Level done -> steps=1. Process (0,0): neighbor (1,0)=1 -> hit island 2!
return steps = 1

What must stay true

Multi-source BFS from all cells of island 1 expands outward uniformly. The first cell of island 2 reached gives the minimum distance — no need to check all pairs. When you keep that truth intact, each local choice supports the larger solution instead of fighting it.

Shape of the loop

find first land cell, DFS-flood it -> mark as 2, push every cell into queue
steps = 0
while queue not empty:
    for each cell in current level:
        for nbr in 4 directions:
            if nbr == 1: return steps        # reached island 2
            if nbr == 0: mark 2, enqueue
    steps += 1

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Not distinguishing the two islands — use DFS to find and mark island 1 first, then BFS treats unmarked land cells as water to cross. The fix is usually to return to the meaning of each move, not just the steps themselves.

Graphs Pattern