Shortest Bridge

Medium
455.

Shortest Bridge

Shortest Bridge is a medium coding problem on arrays, depth-first search and matrix, asked in Amazon, Google and Meta interviews.

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 <= 12
  • grid[i].length == grid.length
  • grid contains exactly two islands.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {number}
 */
var shortestBridge = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 12
  • grid[i].length == grid.length
  • grid contains exactly two islands.

Hints for Shortest Bridge

  1. Hint 1

    First find one island with a DFS or BFS and mark all of its cells at distance 0.

  2. Hint 2

    Then run a multi-source BFS outward from every cell of that island at once.

  3. Hint 3

    The first time the frontier touches a 1 that 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

  1. Locate any land cell and DFS to collect the first island into the BFS queue.
  2. 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 -1

Java

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)