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.The key idea in #934 Shortest Bridge is to connect two separate islands in a binary grid by flipping the minimum number of 0s to 1s. A common strategy combines Depth-First Search (DFS) and Breadth-First Search (BFS).
First, scan the matrix to locate the first island. Use DFS to mark all its cells and push them into a queue. This effectively captures the entire boundary of the first island.
Next, perform a multi-source BFS starting from all cells of the first island simultaneously. Expand layer by layer across water cells (0), counting the number of expansions. The moment a cell from the second island (1) is reached, the BFS depth represents the minimum number of flips needed to connect the islands.
This approach works because BFS guarantees the shortest expansion distance in an unweighted grid. The overall time complexity is O(n²), as each cell is processed at most once, with O(n²) space for visited tracking and the queue.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| DFS to mark first island + Multi-source BFS expansion | O(n²) | O(n²) |
NeetCode
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.
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.
1const shortestBridge = function(grid) {
2 const directions = [[1, 0], [0, 1], [-1, 0
In the JavaScript implementation, DFS is initially used to explore and mark the first island. We then deploy BFS to efficiently compute the shortest path needed to connect to the second island.
The iterative nature of JavaScript's array and function syntax ensures clarity and readability, mirroring interpreted language benefits seen in Python.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of the Shortest Bridge problem are common in technical interviews at top companies. It tests understanding of graph traversal, grid problems, and the ability to combine DFS and BFS effectively.
The optimal approach uses a combination of DFS and BFS. DFS is first used to mark all cells of one island, and then a multi-source BFS expands outward until it reaches the second island. The BFS layer count gives the minimum number of flips required.
DFS helps identify and mark all cells belonging to the first island efficiently. BFS is then used to expand outward level by level across water cells, ensuring the shortest path to the second island is found.
A queue is essential for the BFS traversal because it processes cells in layers. Additionally, a visited matrix or in-place marking in the grid helps avoid revisiting cells during both DFS and BFS steps.