Shortest Bridge — Solution in Python, Java & C++
Shortest Bridge solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Shortest Bridge is a medium coding problem on arrays, depth-first search and matrix, asked in Amazon, Google and Meta interviews.
- Difficulty: Medium
- Topics: Arrays, Depth-First Search, Matrix, Breadth-First Search
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an n x n binary matrix grid containing exactly two islands, where an island is a maximal group of 1s connected up, down, left or right.
Return the smallest number of 0s you must flip to 1 to join 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
2 <= grid.length <= 12grid[i].length == grid.lengthgrid contains exactly two islands.
Hints for Shortest Bridge
Hint 1
First find one island with a DFS or BFS and mark all of its cells at distance 0.
Hint 2
Then run a multi-source BFS outward from every cell of that island at once.
Hint 3
The first time the frontier touches a
1that is not part of the first island, you have the answer.
How to solve Shortest Bridge
Find one island with a DFS and mark its cells at distance 0, then multi-source BFS outward; the first expansion that touches the other island gives the answer.
Approach
- Locate any land cell and DFS to collect the first island into the BFS queue.
- BFS through water; when a neighbour is land not yet visited, return the current distance.
Why it works
BFS from the whole first island computes the minimum number of water cells between it and any other cell, and the first land cell reached belongs to the second island.
Complexity
- Time —
O(n²) - Space —
O(n²)
Pitfalls
- Mark the first island fully before starting the BFS, or its own cells are mistaken for the target.
Reference solution
Python
from collections import deque
def shortestBridge(grid) -> int:
n = len(grid)
dist = [[-1] * n for _ in range(n)]
queue = deque()
start = None
for r in range(n):
for c in range(n):
if grid[r][c] == 1:
start = (r, c)
break
if start:
break
stack = [start]
dist[start[0]][start[1]] = 0
queue.append(start)
while stack:
r, c = stack.pop()
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 1 and dist[nr][nc] == -1:
dist[nr][nc] = 0
stack.append((nr, nc))
queue.append((nr, nc))
while queue:
r, c = queue.popleft()
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < n and 0 <= nc < n and dist[nr][nc] == -1:
if grid[nr][nc] == 1:
return dist[r][c]
dist[nr][nc] = dist[r][c] + 1
queue.append((nr, nc))
return -1Java
public static int shortestBridge(int[][] grid) {
int n = grid.length;
int[] dr = {1, -1, 0, 0};
int[] dc = {0, 0, 1, -1};
int[][] dist = new int[n][n];
for (int[] row : dist) Arrays.fill(row, -1);
List<int[]> queue = new ArrayList<>();
boolean started = false;
for (int r = 0; r < n && !started; r++) {
for (int c = 0; c < n && !started; c++) {
if (grid[r][c] != 1) continue;
started = true;
dist[r][c] = 0;
Deque<int[]> stack = new ArrayDeque<>();
stack.push(new int[]{r, c});
queue.add(new int[]{r, c});
while (!stack.isEmpty()) {
int[] cell = stack.pop();
for (int d = 0; d < 4; d++) {
int nr = cell[0] + dr[d], nc = cell[1] + dc[d];
if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
if (grid[nr][nc] != 1 || dist[nr][nc] != -1) continue;
dist[nr][nc] = 0;
stack.push(new int[]{nr, nc});
queue.add(new int[]{nr, nc});
}
}
}
}
int head = 0;
while (head < queue.size()) {
int[] cur = queue.get(head++);
for (int d = 0; d < 4; d++) {
int nr = cur[0] + dr[d], nc = cur[1] + dc[d];
if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
if (dist[nr][nc] != -1) continue;
if (grid[nr][nc] == 1) return dist[cur[0]][cur[1]];
dist[nr][nc] = dist[cur[0]][cur[1]] + 1;
queue.add(new int[]{nr, nc});
}
}
return -1;
}C++
int shortestBridge(vector<vector<int>>& grid) {
int n = (int) grid.size();
int dr[4] = {1, -1, 0, 0};
int dc[4] = {0, 0, 1, -1};
vector<vector<int>> dist(n, vector<int>(n, -1));
vector<pair<int,int>> queue;
bool started = false;
for (int r = 0; r < n && !started; r++) {
for (int c = 0; c < n && !started; c++) {
if (grid[r][c] != 1) continue;
started = true;
dist[r][c] = 0;
vector<pair<int,int>> stack;
stack.push_back(make_pair(r, c));
queue.push_back(make_pair(r, c));
while (!stack.empty()) {
pair<int,int> cell = stack.back();
stack.pop_back();
for (int d = 0; d < 4; d++) {
int nr = cell.first + dr[d], nc = cell.second + dc[d];
if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
if (grid[nr][nc] != 1 || dist[nr][nc] != -1) continue;
dist[nr][nc] = 0;
stack.push_back(make_pair(nr, nc));
queue.push_back(make_pair(nr, nc));
}
}
}
}
size_t head = 0;
while (head < queue.size()) {
pair<int,int> cur = queue[head++];
for (int d = 0; d < 4; d++) {
int nr = cur.first + dr[d], nc = cur.second + dc[d];
if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
if (dist[nr][nc] != -1) continue;
if (grid[nr][nc] == 1) return dist[cur.first][cur.second];
dist[nr][nc] = dist[cur.first][cur.second] + 1;
queue.push_back(make_pair(nr, nc));
}
}
return -1;
}JavaScript
var shortestBridge = function(grid) {
const n = grid.length;
const dr = [1, -1, 0, 0], dc = [0, 0, 1, -1];
const dist = [];
for (let r = 0; r < n; r++) {
const row = [];
for (let c = 0; c < n; c++) row.push(-1);
dist.push(row);
}
const queue = [];
let started = false;
for (let r = 0; r < n && !started; r++) {
for (let c = 0; c < n && !started; c++) {
if (grid[r][c] !== 1) continue;
started = true;
dist[r][c] = 0;
const stack = [[r, c]];
queue.push([r, c]);
while (stack.length > 0) {
const cell = stack.pop();
for (let d = 0; d < 4; d++) {
const nr = cell[0] + dr[d], nc = cell[1] + dc[d];
if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
if (grid[nr][nc] !== 1 || dist[nr][nc] !== -1) continue;
dist[nr][nc] = 0;
stack.push([nr, nc]);
queue.push([nr, nc]);
}
}
}
}
let head = 0;
while (head < queue.length) {
const cell = queue[head++];
for (let d = 0; d < 4; d++) {
const nr = cell[0] + dr[d], nc = cell[1] + dc[d];
if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
if (dist[nr][nc] !== -1) continue;
if (grid[nr][nc] === 1) return dist[cell[0]][cell[1]];
dist[nr][nc] = dist[cell[0]][cell[1]] + 1;
queue.push([nr, nc]);
}
}
return -1;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Depth-First Search (DFS)