Watch 10 video solutions for Shortest Bridge, a medium level problem involving Array, Depth-First Search, Breadth-First Search. This walkthrough by NeetCode has 48,135 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 1's not connected to any other 1's. There are exactly two islands in grid.
You may change 0's to 1's to connect the two islands to form one island.
Return the smallest number of 0's you must flip to connect the two islands.
Example 1:
Input: grid = [[0,1],[1,0]] Output: 1
Example 2:
Input: grid = [[0,1,0],[0,0,0],[0,0,1]] Output: 2
Example 3:
Input: 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]] Output: 1
Constraints:
n == grid.length == grid[i].length2 <= n <= 100grid[i][j] is either 0 or 1.grid.Problem Overview: You are given an n x n binary grid with exactly two islands (groups of connected 1s). The task is to flip the minimum number of 0s to 1s so the two islands become connected. The answer is the length of the shortest bridge between them.
Approach 1: Brute Force Expansion from Every Island Cell (O(n^4) time, O(n^2) space)
First collect all cells belonging to the first island using a traversal such as depth-first search. For each of those cells, run a separate breadth-first search over the matrix to find the nearest cell of the second island. Each BFS explores outward layer by layer through water cells until land from the other island appears.
This works because BFS guarantees the shortest distance from a starting cell. However, running BFS independently from many cells causes repeated exploration of the same water regions. With up to O(n^2) starting points and each BFS costing O(n^2), the overall cost becomes O(n^4).
Approach 2: DFS to Mark First Island + Multi‑Source BFS (O(n^2) time, O(n^2) space)
This is the standard optimal solution. First scan the grid until you find the first 1. Run DFS to mark the entire island and push all its coordinates into a queue. Mark them as visited so they are not processed again.
Next perform a multi‑source BFS starting from every cell of the first island simultaneously. Each BFS layer represents flipping one additional ring of water cells. For every step, expand in four directions and convert reachable 0 cells to visited water. The moment a neighbor cell with value 1 from the second island is encountered, the current BFS level is the minimum number of flips required.
The key insight: instead of running BFS from each island cell separately, treat the entire first island as the starting frontier. This guarantees the shortest bridge while exploring each grid cell at most once. Time complexity becomes O(n^2) with O(n^2) space for the queue and visited tracking.
Recommended for interviews: Interviewers expect the DFS + multi‑source BFS approach. Detecting the first island with DFS shows comfort with grid traversal, and expanding with BFS demonstrates understanding of shortest path in an unweighted grid. Mentioning the brute force idea briefly helps show the reasoning path, but implementing the optimized BFS expansion is the real signal of problem‑solving skill.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force BFS from Each Island Cell | O(n^4) | O(n^2) | Conceptual baseline to understand why repeated BFS searches are inefficient |
| DFS + Multi‑Source BFS (Optimal) | O(n^2) | O(n^2) | Standard solution for grid shortest‑path problems where all edges have equal cost |