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.
This approach involves two primary steps:
1. Use DFS to mark one of the islands completely.
2. Use BFS from the boundary of that marked island to find the shortest path to the other island.
The BFS will expand layer by layer, counting the zeros flipped until the boundary of the second island is reached.
This solution first uses DFS to mark all the cells of the first island. Each cell belonging to the island is added to a queue.
By using DFS for marking, we ensure all island cells are explored. Once marked, a BFS is used to expand outwards from all boundary points simultaneously, effectively finding the shortest path to the second island.
Time Complexity: O(N^2), where N is the size of the grid, because each cell is processed at most twice (once in DFS and once in BFS).
Space Complexity: O(N^2), for the visited array and the queue holding grid indices.
| 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 |
Shortest Bridge - Leetcode 934 - Python • NeetCode • 48,135 views views
Watch 9 more video solutions →Practice Shortest Bridge with our built-in code editor and test cases.
Practice on FleetCode