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:

1
2
3
4


Input:
grid = [[0,1],[1,0]]
Output:
 1

Example 2:

1
2
3
4


Input:
grid = [[0,1,0],[0,0,0],[0,0,1]]
Output:
 2

Example 3:

1
2
3
4


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


#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;
	}
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43


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);
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


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
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


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
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


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) where n is the grid size (each cell is visited at most once).
🧺 Space complexity: O(n^2) for the visited structure and queue.

Shortest Bridge Problem#

Problem#

Examples#

Solution#

Method 1 – DFS + BFS#

Intuition#

Approach#

Code#

Complexity#