Shortest Bridge
MediumUpdated: Aug 2, 2025
Practice on:
Shortest Bridge Problem
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.
Examples
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
Solution
Method 1 – DFS + BFS
Intuition
To connect the two islands with the shortest bridge, we first mark all cells of one island using DFS. Then, we use BFS to expand outward from this island, layer by layer, until we reach the other island. The number of BFS layers traversed gives the minimum number of 0's to flip.
Approach
- Use DFS to find and mark all cells of the first island, adding their coordinates to a queue.
- Use BFS from all marked cells, expanding outward and counting steps until a cell of the second island is reached.
Code
C++
#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
int shortestBridge(vector<vector<int>>& A) {
int m = A.size(), n = A[0].size();
vector<vector<bool>> vis(m, vector<bool>(n));
queue<pair<int,int>> q;
int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
bool found = false;
auto dfs = [&](int i, int j, auto&& dfs_ref) -> void {
if (i<0||j<0||i>=m||j>=n||vis[i][j]||A[i][j]==0) return;
vis[i][j]=true; q.emplace(i,j);
for (auto& d : dirs) dfs_ref(i+d[0],j+d[1],dfs_ref);
};
for (int i=0; i<m && !found; ++i)
for (int j=0; j<n && !found; ++j)
if (A[i][j]==1) { dfs(i,j,dfs); found=true; }
int step=0;
while (!q.empty()) {
int sz=q.size();
while (sz--) {
auto [x,y]=q.front(); q.pop();
for (auto& d : dirs) {
int ni=x+d[0], nj=y+d[1];
if (ni>=0&&nj>=0&&ni<m&&nj<n&&!vis[ni][nj]) {
if (A[ni][nj]==1) return step;
q.emplace(ni,nj); vis[ni][nj]=true;
}
}
}
++step;
}
return -1;
}
};
Go
func shortestBridge(A [][]int) int {
m, n := len(A), len(A[0])
vis := make([][]bool, m)
for i := range vis { vis[i] = make([]bool, n) }
dirs := [][2]int{{1,0},{-1,0},{0,1},{0,-1}}
q := [][2]int{}
var dfs func(i, j int)
found := false
dfs = func(i, j int) {
if i<0||j<0||i>=m||j>=n||vis[i][j]||A[i][j]==0 { return }
vis[i][j]=true; q = append(q, [2]int{i,j})
for _, d := range dirs { dfs(i+d[0], j+d[1]) }
}
for i:=0; i<m && !found; i++ {
for j:=0; j<n && !found; j++ {
if A[i][j]==1 { dfs(i,j); found=true }
}
}
step := 0
for len(q)>0 {
sz := len(q)
for k:=0; k<sz; k++ {
x, y := q[0][0], q[0][1]; q = q[1:]
for _, d := range dirs {
ni, nj := x+d[0], y+d[1]
if ni>=0&&nj>=0&&ni<m&&nj<n&&!vis[ni][nj] {
if A[ni][nj]==1 { return step }
q = append(q, [2]int{ni,nj}); vis[ni][nj]=true
}
}
}
step++
}
return -1
}
Java
import java.util.*;
class Solution {
public int shortestBridge(int[][] A) {
int m = A.length, n = A[0].length;
boolean[][] visited = new boolean[m][n];
int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
Queue<int[]> q = new LinkedList<>();
boolean found = false;
for (int i = 0; i < m && !found; i++) {
for (int j = 0; j < n; j++) {
if (A[i][j] == 1) {
dfs(A, visited, q, i, j, dirs);
found = true;
break;
}
}
}
int step = 0;
while (!q.isEmpty()) {
int size = q.size();
while (size-- > 0) {
int[] cur = q.poll();
for (int[] dir : dirs) {
int i = cur[0] + dir[0];
int j = cur[1] + dir[1];
if (i >= 0 && j >= 0 && i < m && j < n && !visited[i][j]) {
if (A[i][j] == 1) return step;
q.offer(new int[]{i, j});
visited[i][j] = true;
}
}
}
step++;
}
return -1;
}
private void dfs(int[][] A, boolean[][] visited, Queue<int[]> q, int i, int j, int[][] dirs) {
if (i < 0 || j < 0 || i >= A.length || j >= A[0].length || visited[i][j] || A[i][j] == 0) return;
visited[i][j] = true;
q.offer(new int[]{i, j});
for (int[] dir : dirs) dfs(A, visited, q, i + dir[0], j + dir[1], dirs);
}
}
Kotlin
import java.util.*
class Solution {
fun shortestBridge(A: Array<IntArray>): Int {
val m = A.size; val n = A[0].size
val vis = Array(m) { BooleanArray(n) }
val dirs = arrayOf(intArrayOf(1,0), intArrayOf(-1,0), intArrayOf(0,1), intArrayOf(0,-1))
val q: Queue<Pair<Int,Int>> = LinkedList()
var found = false
fun dfs(i: Int, j: Int) {
if (i !in 0 until m || j !in 0 until n || vis[i][j] || A[i][j]==0) return
vis[i][j]=true; q.add(i to j)
for (d in dirs) dfs(i+d[0], j+d[1])
}
for (i in 0 until m) {
if (found) break
for (j in 0 until n) {
if (A[i][j]==1) { dfs(i,j); found=true; break }
}
}
var step = 0
while (q.isNotEmpty()) {
repeat(q.size) {
val (x, y) = q.poll()
for (d in dirs) {
val ni = x+d[0]; val nj = y+d[1]
if (ni in 0 until m && nj in 0 until n && !vis[ni][nj]) {
if (A[ni][nj]==1) return step
q.add(ni to nj); vis[ni][nj]=true
}
}
}
step++
}
return -1
}
}
Python
from collections import deque
class Solution:
def shortestBridge(self, A: list[list[int]]) -> int:
m, n = len(A), len(A[0])
vis = [[False]*n for _ in range(m)]
q = deque()
dirs = [(1,0),(-1,0),(0,1),(0,-1)]
found = False
def dfs(i, j):
if i<0 or j<0 or i>=m or j>=n or vis[i][j] or A[i][j]==0: return
vis[i][j]=True; q.append((i,j))
for d in dirs: dfs(i+d[0], j+d[1])
for i in range(m):
if found: break
for j in range(n):
if A[i][j]==1:
dfs(i,j); found=True; break
step = 0
while q:
for _ in range(len(q)):
x, y = q.popleft()
for dx, dy in dirs:
ni, nj = x+dx, y+dy
if 0<=ni<m and 0<=nj<n and not vis[ni][nj]:
if A[ni][nj]==1: return step
q.append((ni,nj)); vis[ni][nj]=True
step += 1
return -1
Rust
use std::collections::VecDeque;
impl Solution {
pub fn shortest_bridge(a: Vec<Vec<i32>>) -> i32 {
let m = a.len(); let n = a[0].len();
let mut vis = vec![vec![false;n];m];
let dirs = [(1,0),(-1,0),(0,1),(0,-1)];
let mut q = VecDeque::new();
let mut found = false;
fn dfs(a: &Vec<Vec<i32>>, vis: &mut Vec<Vec<bool>>, q: &mut VecDeque<(usize,usize)>, i: isize, j: isize, m: usize, n: usize, dirs: &[(isize,isize)]) {
if i<0||j<0||i>=m as isize||j>=n as isize||vis[i as usize][j as usize]||a[i as usize][j as usize]==0 { return; }
vis[i as usize][j as usize]=true; q.push_back((i as usize,j as usize));
for &(dx,dy) in dirs { dfs(a, vis, q, i+dx, j+dy, m, n, dirs); }
}
'outer: for i in 0..m {
for j in 0..n {
if a[i][j]==1 { dfs(&a, &mut vis, &mut q, i as isize, j as isize, m, n, &dirs); found=true; break 'outer }
}
}
let mut step = 0;
while !q.is_empty() {
for _ in 0..q.len() {
let (x,y) = q.pop_front().unwrap();
for &(dx,dy) in &dirs {
let ni = x as isize + dx; let nj = y as isize + dy;
if ni>=0&&nj>=0&&ni<m as isize&&nj<n as isize&&!vis[ni as usize][nj as usize] {
if a[ni as usize][nj as usize]==1 { return step; }
q.push_back((ni as usize, nj as usize)); vis[ni as usize][nj as usize]=true;
}
}
}
step += 1;
}
-1
}
}
TypeScript
function shortestBridge(A: number[][]): number {
const m = A.length, n = A[0].length;
const vis: boolean[][] = Array.from({length: m}, () => Array(n).fill(false));
const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
const q: [number, number][] = [];
let found = false;
function dfs(i: number, j: number) {
if (i<0||j<0||i>=m||j>=n||vis[i][j]||A[i][j]===0) return;
vis[i][j]=true; q.push([i,j]);
for (const [dx,dy] of dirs) dfs(i+dx, j+dy);
}
for (let i=0; i<m && !found; i++)
for (let j=0; j<n && !found; j++)
if (A[i][j]===1) { dfs(i,j); found=true; }
let step = 0;
while (q.length) {
let sz = q.length;
while (sz--) {
const [x, y] = q.shift()!;
for (const [dx,dy] of dirs) {
const ni = x+dx, nj = y+dy;
if (ni>=0&&nj>=0&&ni<m&&nj<n&&!vis[ni][nj]) {
if (A[ni][nj]===1) return step;
q.push([ni,nj]); vis[ni][nj]=true;
}
}
}
step++;
}
return -1;
}
Complexity
- ⏰ Time complexity:
O(n^2)wherenis the grid size (each cell is visited at most once). - 🧺 Space complexity:
O(n^2)for the visited structure and queue.