LeetCode 934 - Shortest Bridge
The problem gives us an n x n binary matrix called grid. Each cell contains either 1 or 0. A value of 1 represents land, and a value of 0 represents water. Land cells that are connected vertically or horizontally form an island.
Difficulty: 🟡 Medium
Topics: Array, Depth-First Search, Breadth-First Search, Matrix
Solution
Problem Understanding
The problem gives us an n x n binary matrix called grid. Each cell contains either 1 or 0.
A value of 1 represents land, and a value of 0 represents water. Land cells that are connected vertically or horizontally form an island. The problem guarantees that there are exactly two separate islands in the grid.
Our goal is to connect these two islands by flipping water cells into land cells. Each flip changes one 0 into 1. We must determine the minimum number of flips required so that the two islands become connected into one larger island.
The key detail is that we are not asked to return the actual bridge or path. We only need the minimum number of water cells that must be converted.
For example, in this grid:
0 1
1 0
the two islands are diagonally separated. Flipping either water cell creates a connection, so the answer is 1.
The constraints are important:
2 <= n <= 100- The grid contains exactly two islands
Since the grid size is at most 100 x 100, there are at most 10,000 cells. This size is small enough for graph traversal algorithms like Depth-First Search (DFS) and Breadth-First Search (BFS), both of which run comfortably within limits.
Several edge cases are important:
- The islands may already be extremely close, separated by only one water cell.
- One island may completely surround the other.
- Islands may have irregular shapes rather than simple rectangles.
- The shortest bridge may not come from the visually closest pair of cells unless explored systematically.
- A naive search from every cell of one island to every cell of the other island can become unnecessarily expensive.
The guarantee that there are exactly two islands simplifies the logic significantly because we never need to handle more than two connected components.
Approaches
Brute Force Approach
A brute force solution would first identify all cells belonging to the first island and all cells belonging to the second island.
After collecting both sets of coordinates, we could compute the Manhattan distance between every pair of cells across the two islands:
distance = abs(r1 - r2) + abs(c1 - c2) - 1
The subtraction by 1 accounts for the fact that land cells themselves do not need to be flipped.
This approach works because any valid bridge corresponds to a path between one cell from the first island and one cell from the second island. The minimum such distance gives the answer.
However, this approach is inefficient because each island could contain up to O(n^2) cells. Comparing every pair leads to O(n^4) time complexity in the worst case.
For n = 100, this could become very expensive.
Optimal Approach
The key insight is that this problem is really asking for the shortest expansion from one island until we reach the other island.
This naturally suggests a multi-source BFS.
The optimal strategy works in two phases:
- Use DFS (or BFS) to locate and mark all cells of the first island.
- Start a BFS simultaneously from every cell of that island, expanding outward layer by layer through water cells.
The moment the BFS reaches a cell belonging to the second island, the current BFS distance represents the minimum number of flips required.
Why does BFS work so well here?
Because BFS explores all positions at distance 1 before distance 2, all positions at distance 2 before distance 3, and so on. Therefore, the first time we touch the second island, we are guaranteed to have found the shortest bridge.
This reduces the complexity to O(n^2) because each cell is processed at most once.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n^4) | O(n^2) | Compare every pair of island cells |
| Optimal | O(n^2) | O(n^2) | DFS to find first island, BFS to expand outward |
Algorithm Walkthrough
- Traverse the grid until we find the first land cell.
We need a starting point for the first island. As soon as we encounter a 1, we stop searching and begin DFS from that cell.
2. Perform DFS to mark the entire first island.
During DFS:
- Mark every visited island cell
- Add every island cell into a BFS queue
We use DFS because it efficiently explores all connected land cells. 3. Initialize BFS using all cells from the first island.
This is called multi-source BFS because the search starts simultaneously from every cell of the first island.
This is important because the shortest bridge could originate from any edge of the island. 4. Expand outward level by level.
For each BFS layer:
- Explore the four directions
- Skip out-of-bounds cells
- Skip already visited cells
- Handle water cells.
If the neighboring cell is water (0):
- Mark it visited
- Add it to the queue
This represents flipping that water cell into land. 6. Detect the second island.
If we encounter a land cell (1) that was not part of the first island, then we have reached the second island.
The current BFS distance is the minimum number of flips required. 7. Return the BFS level.
Since BFS expands in increasing order of distance, the first successful connection is guaranteed to be optimal.
Why it works
DFS correctly identifies every cell belonging to the first island. BFS then expands uniformly outward from all boundary points simultaneously. Because BFS explores positions in order of increasing distance, the first time it reaches the second island corresponds to the minimum number of water cells that must be flipped. No shorter bridge can exist because BFS would have discovered it earlier.
Python Solution
from collections import deque
from typing import List
class Solution:
def shortestBridge(self, grid: List[List[int]]) -> int:
n = len(grid)
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
visited = set()
queue = deque()
def dfs(row: int, col: int) -> None:
if (
row < 0
or row >= n
or col < 0
or col >= n
or (row, col) in visited
or grid[row][col] == 0
):
return
visited.add((row, col))
queue.append((row, col))
for dr, dc in directions:
dfs(row + dr, col + dc)
found = False
for row in range(n):
if found:
break
for col in range(n):
if grid[row][col] == 1:
dfs(row, col)
found = True
break
steps = 0
while queue:
for _ in range(len(queue)):
row, col = queue.popleft()
for dr, dc in directions:
new_row = row + dr
new_col = col + dc
if (
new_row < 0
or new_row >= n
or new_col < 0
or new_col >= n
or (new_row, new_col) in visited
):
continue
if grid[new_row][new_col] == 1:
return steps
visited.add((new_row, new_col))
queue.append((new_row, new_col))
steps += 1
return -1
The implementation begins by defining the four possible movement directions. Since islands are connected only vertically and horizontally, diagonal movement is never considered.
The visited set prevents revisiting cells during both DFS and BFS. This avoids infinite loops and redundant processing.
The DFS function identifies the first island. Every discovered land cell is both marked visited and added to the BFS queue. This prepares the multi-source BFS initialization.
After the first island is completely discovered, BFS begins. The variable steps tracks how many water layers have been expanded.
Each BFS layer corresponds to flipping one additional layer of water cells. When BFS reaches a new land cell that was not part of the first island, we immediately return the current number of steps.
The final return -1 is technically unreachable because the problem guarantees exactly two islands.
Go Solution
package main
func shortestBridge(grid [][]int) int {
n := len(grid)
directions := [][]int{
{1, 0},
{-1, 0},
{0, 1},
{0, -1},
}
type Pair struct {
row int
col int
}
queue := []Pair{}
visited := make([][]bool, n)
for i := 0; i < n; i++ {
visited[i] = make([]bool, n)
}
var dfs func(int, int)
dfs = func(row int, col int) {
if row < 0 || row >= n || col < 0 || col >= n {
return
}
if visited[row][col] || grid[row][col] == 0 {
return
}
visited[row][col] = true
queue = append(queue, Pair{row, col})
for _, dir := range directions {
dfs(row+dir[0], col+dir[1])
}
}
found := false
for row := 0; row < n; row++ {
if found {
break
}
for col := 0; col < n; col++ {
if grid[row][col] == 1 {
dfs(row, col)
found = true
break
}
}
}
steps := 0
for len(queue) > 0 {
size := len(queue)
for i := 0; i < size; i++ {
current := queue[0]
queue = queue[1:]
for _, dir := range directions {
newRow := current.row + dir[0]
newCol := current.col + dir[1]
if newRow < 0 || newRow >= n || newCol < 0 || newCol >= n {
continue
}
if visited[newRow][newCol] {
continue
}
if grid[newRow][newCol] == 1 {
return steps
}
visited[newRow][newCol] = true
queue = append(queue, Pair{newRow, newCol})
}
}
steps++
}
return -1
}
The Go implementation follows the same overall logic as the Python solution.
Since Go does not have tuples, a custom Pair struct stores coordinates. Instead of a Python set, a two-dimensional boolean slice tracks visited cells.
Go slices are used as queues by removing elements from the front with:
queue = queue[1:]
The algorithm remains identical in behavior and complexity.
Worked Examples
Example 1
grid = [
[0,1],
[1,0]
]
Initial grid:
| Row | Values |
|---|---|
| 0 | [0,1] |
| 1 | [1,0] |
DFS finds the first island at (0,1).
Visited after DFS:
| Visited Cells |
|---|
| (0,1) |
Initial BFS queue:
| Queue |
|---|
| [(0,1)] |
BFS Level 0:
Explore neighbors of (0,1):
| Neighbor | Value | Action |
|---|---|---|
| (1,1) | 0 | Add to queue |
| (0,0) | 0 | Add to queue |
Queue after level:
| Queue |
|---|
| [(1,1), (0,0)] |
Increment steps to 1.
BFS Level 1:
Process (1,1):
| Neighbor | Value | Action |
|---|---|---|
| (1,0) | 1 | Second island found |
Return 1.
Example 2
grid = [
[0,1,0],
[0,0,0],
[0,0,1]
]
First island discovered:
| Visited |
|---|
| (0,1) |
BFS expansion:
| Step | Expanded Cells |
|---|---|
| 0 | (0,1) |
| 1 | (0,0), (0,2), (1,1) |
| 2 | (1,0), (1,2), (2,1) |
From (1,2), BFS reaches (2,2) which belongs to the second island.
Return 2.
Example 3
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]
]
The outer ring forms the first island.
The center cell (2,2) forms the second island.
BFS starts from all outer island cells simultaneously.
At distance 1, BFS reaches one of the surrounding water cells adjacent to (2,2).
From there, the second island is immediately reached.
Return 1.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n^2) | Each cell is visited at most once during DFS and BFS |
| Space | O(n^2) | Queue and visited structure may store all cells |
The DFS traversal processes each land cell of the first island once. The BFS traversal also processes each cell at most once because visited cells are never revisited.
Although DFS and BFS are separate phases, together they still touch each cell only a constant number of times, giving an overall time complexity of O(n^2).
The auxiliary space complexity is also O(n^2) because the visited structure and BFS queue may both contain a large portion of the grid.
Test Cases
from typing import List
from collections import deque
class Solution:
def shortestBridge(self, grid: List[List[int]]) -> int:
n = len(grid)
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
visited = set()
queue = deque()
def dfs(row: int, col: int) -> None:
if (
row < 0
or row >= n
or col < 0
or col >= n
or (row, col) in visited
or grid[row][col] == 0
):
return
visited.add((row, col))
queue.append((row, col))
for dr, dc in directions:
dfs(row + dr, col + dc)
found = False
for row in range(n):
if found:
break
for col in range(n):
if grid[row][col] == 1:
dfs(row, col)
found = True
break
steps = 0
while queue:
for _ in range(len(queue)):
row, col = queue.popleft()
for dr, dc in directions:
new_row = row + dr
new_col = col + dc
if (
new_row < 0
or new_row >= n
or new_col < 0
or new_col >= n
or (new_row, new_col) in visited
):
continue
if grid[new_row][new_col] == 1:
return steps
visited.add((new_row, new_col))
queue.append((new_row, new_col))
steps += 1
return -1
solution = Solution()
assert solution.shortestBridge([[0,1],[1,0]]) == 1
# Smallest possible bridge
assert solution.shortestBridge([
[0,1,0],
[0,0,0],
[0,0,1]
]) == 2
# Requires two flips
assert solution.shortestBridge([
[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]
]) == 1
# One island surrounds another
assert solution.shortestBridge([
[1,0,0],
[0,0,0],
[0,0,1]
]) == 3
# Maximum separation in small grid
assert solution.shortestBridge([
[1,1],
[0,1]
]) == -1
# Invalid according to constraints, included for robustness
assert solution.shortestBridge([
[1,1,0,0],
[1,0,0,0],
[0,0,0,1],
[0,0,1,1]
]) == 2
# Irregular island shapes
assert solution.shortestBridge([
[1,0,1]
]) == 1
# Single row grid
assert solution.shortestBridge([
[1],
[0],
[1]
]) == 1
# Single column grid
| Test | Why |
|---|---|
[[0,1],[1,0]] |
Smallest valid bridge |
[[0,1,0],[0,0,0],[0,0,1]] |
Requires multiple BFS layers |
| Outer ring with center island | Tests enclosed island scenario |
| Diagonal corner islands | Tests long-distance bridge |
| Invalid single-island case | Checks robustness beyond constraints |
| Irregular island shapes | Ensures DFS handles non-rectangular islands |
| Single row grid | Tests horizontal boundary handling |
| Single column grid | Tests vertical boundary handling |
Edge Cases
One important edge case occurs when the islands are separated by exactly one water cell. A careless implementation might accidentally overcount the number of flips if BFS levels are managed incorrectly. In our solution, BFS increments the step counter only after processing an entire layer, so the first direct connection correctly returns 1.
Another important case is when one island surrounds the other. In this situation, the visually closest path may exist in many directions simultaneously. A single-source search from only one island cell could miss the optimal bridge initially. Multi-source BFS solves this by expanding outward from every cell of the first island at the same time.
Irregular island shapes are another common source of bugs. Islands are not guaranteed to be rectangles or simple structures. DFS ensures that every connected land cell is discovered regardless of shape, because it recursively explores all four directions from every land cell.
Boundary handling is also critical. Cells on the edges or corners of the grid can easily cause index-out-of-range errors if neighbors are accessed carelessly. Both DFS and BFS explicitly validate coordinates before accessing grid values, ensuring safe traversal for all positions.