Shortest Bridge — DFS Find Island + BFS Expand

Problem Statement

LeetCode 934 — Shortest Bridge (Medium)

You are given an n x n binary matrix grid where 1 represents land and 0 represents water. There are exactly two islands in the grid. You may change 0s to 1s to connect the two islands. Return the minimum number of 0s you must flip to connect the two islands.

Constraints:

n == grid.length == grid[i].length
2 <= n <= 100
grid[i][j] is 0 or 1
There are exactly two islands in grid

Example 1:

Input:
0 1
1 0
 
Output: 1
Explanation: Flip one 0 to connect the two single-cell islands.

Example 2:

Input:
0 1 0
0 0 0
0 0 1
 
Output: 2
Explanation: Must flip 2 zeros to build a bridge from (0,1) to (2,2).

Example 3:

Input:
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
Explanation: Flip the single water cell at (2,2) to connect inner and outer land.

Why This Problem Matters

Shortest Bridge is a classic example of algorithm composition — combining two different traversal strategies in sequence to solve a problem neither could handle alone:

DFS is ideal for exploring and marking a complete connected component (island 1)
BFS is ideal for finding the shortest path / minimum expansion distance

The insight that you can "seed" a multi-source BFS from an entire island (rather than just a single point) is the key transferable skill. This pattern — DFS to collect a set of starting nodes, then BFS for shortest distance — appears in many problems:

LC 286 — Walls and Gates (multi-source BFS)
LC 542 — 01 Matrix (multi-source BFS from all zeros)
LC 994 — Rotting Oranges (multi-source BFS from all rotten oranges)

Interviewers use this problem to check whether candidates understand BFS distance semantics: each "level" of BFS expansion represents flipping exactly one more zero, so the first time BFS reaches island 2, the current level number is the answer.

The Core Insight

The problem reduces to: what is the shortest path of water cells between the two islands?

BFS from every cell of island 1 simultaneously (multi-source BFS) gives the shortest distance from any island-1 cell to any island-2 cell. The moment BFS visits a cell belonging to island 2, the current BFS level is the answer.

The two-phase approach:

DFS Phase: Scan until you find any cell of island 1. Flood-fill island 1 using DFS, coloring all its cells with value 2 and adding each to the BFS queue.
BFS Phase: Expand BFS level-by-level from island 1. Water cells get colored 2 (visited). The first time you encounter a cell with value 1 (island 2), return the current level count.

The coloring trick (2 = "island 1 or its BFS expansion") prevents revisiting without a separate visited matrix.

Visual Dry Run

Grid:
0 0 1 1
0 0 0 1
1 0 0 0
1 1 0 0
 
Phase 1: DFS from first '1' found — (0,2)
  DFS visits: (0,2)→2, (0,3)→2, (1,3)→2
  BFS queue seeded: [(0,2), (0,3), (1,3)]
 
Grid after DFS coloring:
0 0 2 2
0 0 0 2
1 0 0 0
1 1 0 0
 
Phase 2: BFS expansion
  Level 0 (initial island): (0,2),(0,3),(1,3) already in queue
  
  Level 1 (steps=0, processing initial queue):
    From (0,2): neighbors (0,1)→water→add, (1,2)→water→add
    From (0,3): neighbors all visited or OOB
    From (1,3): neighbors (2,3)→water→add
    
  Level 1 done. steps becomes 1.
  Queue: [(0,1),(1,2),(2,3)]
  
  Level 2 (steps=1):
    From (0,1): (0,0)→water→add, (1,1)→water→add
    From (1,2): (1,1) already, (2,2)→water→add
    From (2,3): (3,3)→water→add
    
  steps becomes 2. Queue: [(0,0),(1,1),(2,2),(3,3)]
  
  Level 3 (steps=2):
    From (0,0): (1,0) — grid[1][0]=1 → ISLAND 2 FOUND! Return steps=2
 
Answer: 2

Common Mistakes

Not seeding all island-1 cells into the BFS queue. If you only seed one cell of island 1 into BFS, you measure distance from that single cell, not from the closest point of the entire island. Always flood-fill the entire first island and enqueue all of it.
Off-by-one in the BFS level count. The answer is the number of water cells flipped, which equals the BFS level when island 2 is first reached. If you increment steps before processing a level instead of after, you get steps+1.
Checking the wrong termination condition in BFS. You should detect island 2 when you dequeue a cell that has value 1 (the neighbor check hits 1), not when you enqueue it. The standard pattern: when you find a neighbor with value 1, return steps before incrementing.
Missing the DFS break condition. The outer scan that triggers DFS must break once the first island is found. Without it, you'll start DFS from every land cell, potentially re-coloring island 2 as 2 before BFS reaches it.
Using n x n dimensions but accessing grid[0].length instead of n. The problem guarantees a square grid but some solutions hardcode one dimension incorrectly.
Recursion depth exceeded on large grids. DFS with Python's default recursion limit can fail for n = 100 with a large island. Use iterative DFS with an explicit stack, or increase the recursion limit.

Solutions

Python

from collections import deque
 
class Solution:
    def shortestBridge(self, grid: list[list[int]]) -> int:
        n = len(grid)                    # grid is n x n
        q = deque()                      # BFS queue, seeded with all island-1 cells
        found = False                    # flag to stop outer scan after finding island 1
 
        def dfs(r, c):
            # stop if out of bounds, water, or already colored
            if not (0 <= r < n and 0 <= c < n) or grid[r][c] != 1:
                return
            grid[r][c] = 2               # color island 1 as '2'
            q.append((r, c))             # add to BFS starting frontier
            # explore all 4 neighbors
            for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                dfs(r + dr, c + dc)
 
        # Find any cell of island 1 and flood-fill it entirely
        for r in range(n):
            if found:
                break
            for c in range(n):
                if grid[r][c] == 1:
                    dfs(r, c)            # flood-fill entire island 1
                    found = True
                    break
 
        # BFS: expand outward from island 1, level by level
        steps = 0
        while q:
            # process every cell at the current BFS level
            for _ in range(len(q)):
                r, c = q.popleft()
                for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < n and 0 <= nc < n:
                        if grid[nr][nc] == 1:
                            return steps     # reached island 2
                        if grid[nr][nc] == 0:
                            grid[nr][nc] = 2     # mark water as visited
                            q.append((nr, nc))   # add to next BFS level
            steps += 1                   # one more water cell flipped
 
        return steps                     # should never reach here given valid input

JavaScript

/**
 * @param {number[][]} grid
 * @return {number}
 */
var shortestBridge = function(grid) {
    const n = grid.length;               // grid is n x n
    const queue = [];                    // BFS queue (used as array with index pointer)
    let qHead = 0;                       // pointer into queue for O(1) dequeue
    let found = false;                   // stop outer scan once island 1 is seeded
 
    // DFS: color island 1 cells as 2 and add to BFS queue
    function dfs(r, c) {
        if (r < 0 || r >= n || c < 0 || c >= n || grid[r][c] !== 1) return;
        grid[r][c] = 2;                  // mark cell as part of island 1 frontier
        queue.push([r, c]);              // seed into multi-source BFS
        dfs(r + 1, c);                   // explore down
        dfs(r - 1, c);                   // explore up
        dfs(r, c + 1);                   // explore right
        dfs(r, c - 1);                   // explore left
    }
 
    // Find the first land cell of island 1 and flood-fill it
    outer: for (let r = 0; r < n; r++) {
        for (let c = 0; c < n; c++) {
            if (grid[r][c] === 1) {
                dfs(r, c);               // color entire island 1
                found = true;
                break outer;             // exit both loops
            }
        }
    }
 
    // BFS: expand level by level from island 1 toward island 2
    let steps = 0;
    while (qHead < queue.length) {
        const levelSize = queue.length - qHead;  // number of nodes at current level
        for (let i = 0; i < levelSize; i++) {
            const [r, c] = queue[qHead++];       // dequeue front element
            for (const [dr, dc] of [[1,0],[-1,0],[0,1],[0,-1]]) {
                const nr = r + dr;
                const nc = c + dc;
                if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
                    if (grid[nr][nc] === 1) return steps;  // reached island 2
                    if (grid[nr][nc] === 0) {
                        grid[nr][nc] = 2;        // mark water as visited
                        queue.push([nr, nc]);    // add to next BFS level
                    }
                }
            }
        }
        steps++;                         // finished one BFS level (one flip)
    }
 
    return steps;
};

Complexity Analysis

Approach	Time Complexity	Space Complexity
DFS (color island 1) + BFS (expand)	O(n^2)	O(n^2)

Time: DFS visits every cell of island 1 once — O(n^2) worst case. BFS visits every remaining cell at most once — O(n^2). Total: O(n^2).
Space: The BFS queue holds at most O(n^2) cells (all cells at a given BFS frontier). The DFS recursion stack also uses O(n^2) in the worst case if island 1 is large. Using an explicit DFS stack reduces both to O(n^2) with smaller constants.

Follow-up Questions

Three or more islands: The problem specifies exactly two, but if there were more, you'd need to identify all island pairs and use BFS from each — or use Dijkstra's algorithm to find the global minimum bridge.
Larger grids / stack overflow: For n = 1000, recursive DFS would blow Python's stack. Rewrite DFS iteratively: use an explicit stack, pop cells, add neighbors if grid[r][c] == 1.
What if the bridge must be a straight line? This changes the problem to a geometric one — find the minimum distance between the bounding rectangles of the two islands.
What if you can also flip 1s to 0s? This becomes a shortest path problem in a weighted graph where flipping land costs 1 and flipping water costs 1 — Dijkstra with a 0-1 BFS would apply.
LC 286 — Walls and Gates: Similar multi-source BFS seeding pattern, useful to practice adjacently.

This Pattern Solves

Multi-source BFS from a set of starting nodes — any time you need shortest distance from an entire component to another component
LC 542 — 01 Matrix: BFS from all zeros to find distance to nearest zero
LC 994 — Rotting Oranges: Multi-source BFS from all rotten cells
LC 286 — Walls and Gates: Multi-source BFS from all gates

Key Takeaways

Two-phase approach: DFS to color the first island, then multi-source BFS to expand outward until hitting the second island
DFS excels at fully exploring and labeling connected components; BFS excels at finding shortest distance
Seed the BFS queue with every cell of island 1 — this is multi-source BFS, not single-source
Color island 1 cells as 2 to act as both "visited" marker and BFS seed — avoids a separate visited array
BFS level count equals the number of water cells flipped (bridge length) — return when island 2 is first reached
Never increment steps before processing the current level — off-by-one is a common bug here
For large grids (n=1000), use iterative DFS with an explicit stack to avoid Python recursion depth limits

Problem Statement#

Why This Problem Matters#

The Core Insight#

Visual Dry Run#

Common Mistakes#

Solutions#

Python#

JavaScript#

Complexity Analysis#

Follow-up Questions#

This Pattern Solves#

Key Takeaways#

Related reading