Shortest Bridge solution and explanation
Google
9 more videos on this problem
Shortest Bridge - Leetcode 934 - PythonNeetCode · 14:51 · 49K views
Shortest Bridge | Leetcode-934 | DFS + BFS | MICROSOFT | Explanation ➕ Live CodingcodestorywithMIK · 26:49 · 8K views
G-13 BFS+DFS Problems II Shortest Bridge II Leetcode 934 II C++/JavaAryan Mittal · 16:45 · 7K views
花花酱 LeetCode 934. Shortest Bridge - 刷题找工作 EP230Hua Hua · 8:40 · 7K views
LeetCode 934. Shortest BridgeHappy Coding · 20:45 · 4K views
Leetcode 934: Shortest BridgeAlgorithms Casts · 52:54 · 1K views
934. Shortest Bridge | Graphs | LeetCode Daily ChallengeDeep Tech · 14:26 · 1K views
934 Shortest Bridge Leetcode | Graph | Leetcode 934 Shortest Bridge | 934 Shortest BridgeAshutosh sharma · 14:36 · 1K views
LeetCode 934. Shortest Bridge | JavaHow we live in Texas · 8:23 · 517 views
Shortest Bridge - LeetCode 934 - Python SolutionCode with Carter · 13:14 · 483 views
The problem
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 either0or1.- There are exactly two islands in
grid.
Approach overview
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 1: Depth-First Search (DFS) and Breadth-First Search (BFS)
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.
from collections import deque
class Solution:
def shortestBridge(self, grid: List[List[int]]) -> int:
directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
def dfs(x, y, queue):
if x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0]) or grid[x][y] != 1:
return
grid[x][y] = 2
queue.append((x, y))
for dx, dy in directions:
dfs(x + dx, y + dy, queue)
n = len(grid)
found = False
queue = deque()
for i in range(n):
for j in range(n):
if grid[i][j] == 1:
dfs(i, j, queue)
found = True
break
if found:
break
steps = 0
while queue:
size = len(queue)
for _ in range(size):
x, y = queue.popleft()
for dx, dy in directions:
nx, ny = x + dx, y + dy
if nx >= 0 and nx < n and ny >= 0 and ny < n:
if grid[nx][ny] == 1:
return steps
elif grid[nx][ny] == 0:
grid[nx][ny] = 2
queue.append((nx, ny))
steps += 1
return -1
# Example usage
solution = Solution()
print(solution.shortestBridge([[0,1],[1,0]])) # Output: 1
print(solution.shortestBridge([[0,1,0],[0,0,0],[0,0,1]])) # Output: 2
print(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]])) # Output: 1import java.util.*;
public class ShortestBridge {
private static final int[][] directions = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
private void dfs(int[][] grid, int x, int y, boolean[][] visited, Queue<int[]> queue) {
int n = grid.length;
if (x < 0 || x >= n || y < 0 || y >= n || visited[x][y] || grid[x][y] == 0) return;
visited[x][y] = true;
queue.offer(new int[]{x, y});
for (int[] dir : directions)
dfs(grid, x + dir[0], y + dir[1], visited, queue);
}
public int shortestBridge(int[][] grid) {
int n = grid.length;
boolean[][] visited = new boolean[n][n];
Queue<int[]> queue = new LinkedList<>();
boolean found = false;
for (int i = 0; !found && i < n; i++) {
for (int j = 0; !found && j < n; j++) {
if (grid[i][j] == 1) {
dfs(grid, i, j, visited, queue);
found = true;
}
}
}
int steps = 0;
while (!queue.isEmpty()) {
int size = queue.size();
while (size-- > 0) {
int[] cell = queue.poll();
int x = cell[0], y = cell[1];
for (int[] dir : directions) {
int newX = x + dir[0], newY = y + dir[1];
if (newX >= 0 && newX < n && newY >= 0 && newY < n && !visited[newX][newY]) {
if (grid[newX][newY] == 1) return steps;
visited[newX][newY] = true;
queue.offer(new int[]{newX, newY});
}
}
}
steps++;
}
return -1;
}
public static void main(String[] args) {
ShortestBridge sb = new ShortestBridge();
int[][] grid1 = {{0, 1}, {1, 0}};
System.out.println(sb.shortestBridge(grid1)); // Expected output: 1
int[][] grid2 = {{0, 1, 0}, {0, 0, 0}, {0, 0, 1}};
System.out.println(sb.shortestBridge(grid2)); // Expected output: 2
int[][] grid3 = {{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}};
System.out.println(sb.shortestBridge(grid3)); // Expected output: 1
}
}#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<vector<int>> directions = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
void dfs(vector<vector<int>>& grid, int x, int y, vector<vector<bool>>& visited, queue<pair<int, int>>& q) {
int n = grid.size();
if (x < 0 || x >= n || y < 0 || y >= n || visited[x][y] || grid[x][y] == 0) return;
visited[x][y] = true;
q.push({x, y});
for (auto dir : directions)
dfs(grid, x + dir[0], y + dir[1], visited, q);
}
int shortestBridge(vector<vector<int>>& grid) {
int n = grid.size();
vector<vector<bool>> visited(n, vector<bool>(n, false));
queue<pair<int, int>> q;
bool found = false;
for (int i = 0; !found && i < n; i++) {
for (int j = 0; !found && j < n; j++) {
if (grid[i][j] == 1) {
dfs(grid, i, j, visited, q);
found = true;
}
}
}
int steps = 0;
while (!q.empty()) {
int size = q.size();
while (size--) {
auto [x, y] = q.front();
q.pop();
for (auto dir : directions) {
int newX = x + dir[0], newY = y + dir[1];
if (newX >= 0 && newX < n && newY >= 0 && newY < n && !visited[newX][newY]) {
if (grid[newX][newY] == 1) return steps;
visited[newX][newY] = true;
q.push({newX, newY});
}
}
}
steps++;
}
return -1;
}
int main() {
vector<vector<int>> grid1 = {{0,1},{1,0}};
cout << shortestBridge(grid1) << endl; // Expected output: 1
vector<vector<int>> grid2 = {{0,1,0},{0,0,0},{0,0,1}};
cout << shortestBridge(grid2) << endl; // Expected output: 2
vector<vector<int>> grid3 = {{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}};
cout << shortestBridge(grid3) << endl; // Expected output: 1
return 0;
}const shortestBridge = function(grid) {
const directions = [[1, 0], [0, 1], [-1, 0], [0, -1]];
const n = grid.length;
const visited = Array.from({ length: n }, () => Array(n).fill(false));
const queue = [];
const dfs = (x, y) => {
if (x < 0 || x >= n || y < 0 || y >= n || visited[x][y] || grid[x][y] === 0) return;
visited[x][y] = true;
queue.push([x, y]);
for (const [dx, dy] of directions) {
dfs(x + dx, y + dy);
}
};
let found = false;
for (let i = 0; !found && i < n; i++) {
for (let j = 0; !found && j < n; j++) {
if (grid[i][j] === 1) {
dfs(i, j);
found = true;
}
}
}
let steps = 0;
while (queue.length > 0) {
const size = queue.length;
for (let k = 0; k < size; k++) {
const [x, y] = queue.shift();
for (const [dx, dy] of directions) {
const newX = x + dx, newY = y + dy;
if (newX >= 0 && newX < n && newY >= 0 && newY < n && !visited[newX][newY]) {
if (grid[newX][newY] === 1) return steps;
visited[newX][newY] = true;
queue.push([newX, newY]);
}
}
}
steps++;
}
return -1;
};
console.log(shortestBridge([[0,1],[1,0]])) // Output: 1
console.log(shortestBridge([[0,1,0],[0,0,0],[0,0,1]])) // Output: 2
console.log(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]])) // Output: 1#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
int directions[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
void dfs(int** grid, int n, int x, int y, int** visited, int* queue, int* queueSize) {
if (x < 0 || x >= n || y < 0 || y >= n || visited[x][y] || grid[x][y] == 0) return;
visited[x][y] = 1;
queue[(*queueSize)++] = x * n + y;
for (int i = 0; i < 4; i++)
dfs(grid, n, x + directions[i][0], y + directions[i][1], visited, queue, queueSize);
}
int shortestBridge(int** grid, int gridSize, int* gridColSize) {
int n = gridSize;
int** visited = (int**) malloc(n * sizeof(int*));
for (int i = 0; i < n; i++)
visited[i] = (int*)calloc(n, sizeof(int));
int* queue = (int*) malloc(n * n * sizeof(int));
int queueSize = 0, head = 0;
bool found = false;
for (int i = 0; !found && i < n; i++) {
for (int j = 0; !found && j < n; j++) {
if (grid[i][j] == 1) {
dfs(grid, n, i, j, visited, queue, &queueSize);
found = true;
}
}
}
int steps = 0;
while (head < queueSize) {
int size = queueSize - head;
while (size--) {
int pos = queue[head++], x = pos / n, y = pos % n;
for (int i = 0; i < 4; i++) {
int newX = x + directions[i][0], newY = y + directions[i][1];
if (newX >= 0 && newX < n && newY >= 0 && newY < n && !visited[newX][newY]) {
if (grid[newX][newY] == 1) return steps;
visited[newX][newY] = 1;
queue[queueSize++] = newX * n + newY;
}
}
}
steps++;
}
return -1;
}
int main() {
int grid1[2][2] = {{0,1},{1,0}};
int* gridPtrs1[2];
for (int i = 0; i < 2; i++) gridPtrs1[i] = grid1[i];
int gridColSize[2] = {2,2};
printf("%d\n", shortestBridge(gridPtrs1, 2, gridColSize)); // Expected output: 1
int grid2[3][3] = {{0,1,0},{0,0,0},{0,0,1}};
int* gridPtrs2[3];
for (int i = 0; i < 3; i++) gridPtrs2[i] = grid2[i];
int gridColSize2[3] = {3,3,3};
printf("%d\n", shortestBridge(gridPtrs2, 3, gridColSize2)); // Expected output: 2
int grid3[5][5] = {{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}};
int* gridPtrs3[5];
for (int i = 0; i < 5; i++) gridPtrs3[i] = grid3[i];
int gridColSize3[5] = {5,5,5,5,5};
printf("%d\n", shortestBridge(gridPtrs3, 5, gridColSize3)); // Expected output: 1
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
private static readonly int[][] directions = new int[][] {
new int[] { 1, 0 }, new int[] { 0, 1 }, new int[] { -1, 0 }, new int[] { 0, -1 }
};
private void DFS(int[][] grid, int x, int y, bool[][] visited, Queue<(int, int)> queue) {
int n = grid.Length;
if (x < 0 || x >= n || y < 0 || y >= n || visited[x][y] || grid[x][y] == 0) return;
visited[x][y] = true;
queue.Enqueue((x, y));
foreach (var dir in directions)
DFS(grid, x + dir[0], y + dir[1], visited, queue);
}
public int ShortestBridge(int[][] grid) {
int n = grid.Length;
bool[][] visited = new bool[n][];
for (int i = 0; i < n; i++) visited[i] = new bool[n];
Queue<(int, int)> queue = new Queue<(int, int)>();
bool found = false;
for (int i = 0; !found && i < n; i++) {
for (int j = 0; !found && j < n; j++) {
if (grid[i][j] == 1) {
DFS(grid, i, j, visited, queue);
found = true;
}
}
}
int steps = 0;
while (queue.Count > 0) {
int size = queue.Count;
for (int i = 0; i < size; i++) {
var (x, y) = queue.Dequeue();
foreach (var dir in directions) {
int newX = x + dir[0], newY = y + dir[1];
if (newX >= 0 && newX < n && newY >= 0 && newY < n && !visited[newX][newY]) {
if (grid[newX][newY] == 1) return steps;
visited[newX][newY] = true;
queue.Enqueue((newX, newY));
}
}
}
steps++;
}
return -1;
}
public static void Main() {
var solution = new Solution();
Console.WriteLine(solution.ShortestBridge(new int[][] { new int[] { 0, 1 }, new int[] { 1, 0 } })); // Output: 1
Console.WriteLine(solution.ShortestBridge(new int[][] { new int[] { 0, 1, 0 }, new int[] { 0, 0, 0 }, new int[] { 0, 0, 1 } })); // Output: 2
Console.WriteLine(solution.ShortestBridge(new int[][] { new int[] { 1, 1, 1, 1, 1 }, new int[] { 1, 0, 0, 0, 1 }, new int[] { 1, 0, 1, 0, 1 }, new int[] { 1, 0, 0, 0, 1 }, new int[] { 1, 1, 1, 1, 1 } })); // Output: 1
}
}The Python solution builds upon the same logical approach of first marking the complete first island using DFS. The BFS starting at the boundary of this island helps to find the shortest path (least flips of 0s into 1s) that connects to the second island. The collections deque is used due to its efficiency in popping elements from the front.
Time Complexity: O(N^2), as the grid is traversed once fully for marking and then for expanding boundary searches.
Space Complexity: O(N^2) is used with the BFS queue storing states.
Approach 2: Default Approach
func shortestBridge(grid [][]int) (ans int) {
n := len(grid)
dirs := []int{-1, 0, 1, 0, -1}
type pair struct{ i, j int }
q := []pair{}
var dfs func(int, int)
dfs = func(i, j int) {
grid[i][j] = 2
q = append(q, pair{i, j})
for k := 0; k < 4; k++ {
x, y := i+dirs[k], j+dirs[k+1]
if x >= 0 && x < n && y >= 0 && y < n && grid[x][y] == 1 {
dfs(x, y)
}
}
}
for i, x := 0, 1; i < n && x == 1; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == 1 {
dfs(i, j)
x = 0
break
}
}
}
for {
for i := len(q); i > 0; i-- {
p := q[0]
q = q[1:]
for k := 0; k < 4; k++ {
x, y := p.i+dirs[k], p.j+dirs[k+1]
if x >= 0 && x < n && y >= 0 && y < n {
if grid[x][y] == 1 {
return
}
if grid[x][y] == 0 {
grid[x][y] = 2
q = append(q, pair{x, y})
}
}
}
}
ans++
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Depth-First Search (DFS) and Breadth-First Search (BFS) | Time Complexity: O(N^2), as the grid is traversed once fully for marking and then for expanding boundary searches. |
| Default Approach | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Shortest Bridge easy or hard?
Shortest Bridge is classified as Medium difficulty on LeetCode. The challenge comes from combining two traversal strategies—DFS to identify an island and BFS to compute the shortest bridge distance across the grid.
Shortest Bridge Python/Java solution
In Python or Java, the typical implementation runs DFS to mark the first island and add its cells to a queue. Then BFS expands outward in four directions using a queue until the second island is reached. Both implementations run in O(n^2) time and use standard grid traversal patterns.
How to solve Shortest Bridge in O(n^2)?
Start by scanning the grid and run DFS from the first land cell to mark the entire island. Push all its coordinates into a queue. Then run a multi-source BFS that expands outward through water cells until a cell from the second island is reached. The BFS level at that moment equals the minimum flips required.
What is the best approach for Shortest Bridge?
The most efficient method uses Depth-First Search to locate and mark the first island, then runs a multi-source Breadth-First Search from all its cells simultaneously. BFS expands through water layer by layer until it reaches the second island. This guarantees the minimum number of flips with O(n^2) time and O(n^2) space complexity.
Is Shortest Bridge asked at Google/Amazon/Meta?
Shortest Bridge is a common medium-level grid traversal problem and variations appear in interviews at companies like Amazon, Google, and Meta. It tests understanding of DFS for island detection and BFS for shortest path in an unweighted grid.
What data structure is used in Shortest Bridge?
The solution primarily uses a queue for Breadth-First Search and recursion or a stack for Depth-First Search. The grid itself acts as the matrix structure, and a visited marker or in-place modification prevents revisiting cells.
What is the time complexity of Shortest Bridge?
The optimal DFS + BFS approach runs in O(n^2) time for an n x n grid. Each cell is visited at most once while marking the first island and during BFS expansion. Space complexity is also O(n^2) due to the queue and visited tracking.