Shortest Bridge LeetCode 934 Guide

LeetCode 934 — Shortest Bridge — gives you an n x n binary matrix where 1 represents land and 0 represents water. The grid contains exactly two islands (connected components of 1s). Return the smallest number of 0s you must flip to 1 to connect the two islands.

The bridge is a path of flipped cells connecting any cell of island A to any cell of island B. The minimum bridge length equals the shortest distance between any cell on one island and any cell on the other. This is a classic multi-source BFS problem.

The approach has two phases: first identify one complete island using DFS or BFS, then expand outward from that entire island simultaneously using multi-source BFS. The first time the expansion reaches a cell belonging to the second island, the current BFS level is the answer.

Scan the grid until you find the first cell with value 1. From that cell, run a DFS (or BFS) to visit all connected 1s. Mark each visited cell with a special value like 2 to distinguish it from the second island. Add every marked cell to a queue for the next phase.

The DFS explores all four directions (up, down, left, right) from each cell. It stops when it hits water (0) or an already-marked cell (2). After the DFS completes, every cell of the first island is marked 2 and enqueued.

This phase runs in O(n^2) time in the worst case if one island covers most of the grid. The queue now contains the entire boundary and interior of the first island, ready for multi-source BFS expansion.

Multi-source BFS starts with all cells of the first island already in the queue at level 0. Each BFS level expands one step outward into water cells. When expanding, flip 0 cells to 2 (marking them as part of the growing bridge) and add them to the queue.

If the expansion reaches a cell with value 1 — a cell belonging to the second island — return the current level. This is the minimum bridge length because BFS guarantees shortest-path discovery in unweighted graphs.

The BFS processes level by level, not cell by cell. Track the current level with a counter that increments after processing all cells at the current distance. This level-by-level processing is what distinguishes multi-source BFS from a standard single-source traversal.

Consider the grid [[0,1,0],[0,0,0],[0,0,1]]. The first island is the single cell at (0,1). The second island is at (2,2). DFS marks (0,1) as 2 and adds it to the queue.

BFS level 1: expand from (0,1) to neighbors. (0,0), (0,2), (1,1) are water — mark as 2, enqueue. None is the second island. Level 2: expand from those three cells. (1,0), (1,2) are water — mark and enqueue. Level 3: expand further. (2,1) is water — enqueue. (2,2) has value 1 — second island found! Return level 2.

Wait — let me recount. From (1,2) at level 2, we reach (2,2) which is 1. So the answer is 2. Each BFS level corresponds to one flipped cell in the bridge. The path is (0,1) → (1,1) → (2,2) or (0,1) → (1,2) → (2,2), both length 2.

In Python, use a deque for the BFS queue. The DFS can be recursive or iterative. Mark visited cells by modifying the grid in-place (setting to 2). The BFS loop processes one level at a time using len(queue) to track level boundaries.

In Java, use a LinkedList or ArrayDeque for the queue. Store cell coordinates as int[] pairs or encode as r*n + c integers. The DFS uses a stack or recursion. The level-by-level BFS pattern is the same: process all cells at the current distance before incrementing.

Both implementations modify the grid in-place to avoid a separate visited array. This is safe because we never need the original grid values again after marking. The in-place approach saves O(n^2) space for the visited set.

Time complexity is O(n^2) where n is the grid dimension. The DFS visits each cell at most once (O(n^2)). The BFS also visits each cell at most once (O(n^2)). Combined, every cell is processed at most twice.

Space complexity is O(n^2) for the BFS queue in the worst case. If one island spans half the grid, the queue initially holds n^2/2 cells. The DFS recursion stack can also reach O(n^2) depth for a spiral-shaped island — use iterative DFS if stack overflow is a concern.

This is optimal — we must examine every cell to determine island boundaries, so O(n^2) is a lower bound. The multi-source BFS finds the shortest bridge without any redundant work.

Shortest Bridge is closely related to Rotting Oranges (LeetCode 994), which also uses multi-source BFS expanding from initial positions. The key difference is that Shortest Bridge needs a DFS preprocessing step to identify the source island.

Walls and Gates (LeetCode 286) and 01 Matrix (LeetCode 542) are other multi-source BFS problems where you start from multiple cells and expand outward. The pattern is always the same: initialize the queue with all source cells, then BFS level by level.

For harder grid problems, try Pacific Atlantic Water Flow (LeetCode 417) which runs two separate multi-source BFS passes and intersects the results. Mastering Shortest Bridge gives you the foundation for all these grid traversal variants.