Shortest Bridge

Problem#

In a binary grid with exactly two islands of 1s, return the minimum number of 0s to flip so the two islands connect.

Examples#

[[0,1],[1,0]] → 1.
[[0,1,0],[0,0,0],[0,0,1]] → 2; [[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]] → 1.

Constraints#

2 <= n <= 100.

Approach#

DFS-flood the first island, pushing all its cells into a BFS queue and marking them as visited. BFS outward by levels through 0s; the first time we touch a 1 (the second island), the current level minus 1 is the answer.

Solution#

class Solution {
    int m, n;
    int dr[4] = {-1, 1, 0, 0}, dc[4] = {0, 0, -1, 1};
public:
    int shortestBridge(vector<vector<int>>& g) {
        m = g.size(); n = g[0].size();
        queue<pair<int,int>> q;
        function<void(int,int)> dfs = [&](int r, int c) {
            if (r < 0 || r >= m || c < 0 || c >= n || g[r][c] != 1) return;
            g[r][c] = 2;
            q.push({r, c});
            for (int k = 0; k < 4; ++k) dfs(r + dr[k], c + dc[k]);
        };
        bool found = false;
        for (int i = 0; i < m && !found; ++i)
            for (int j = 0; j < n && !found; ++j)
                if (g[i][j] == 1) { dfs(i, j); found = true; }
        int steps = 0;
        while (!q.empty()) {
            int sz = q.size();
            while (sz--) {
                auto [r, c] = q.front(); q.pop();
                for (int k = 0; k < 4; ++k) {
                    int nr = r + dr[k], nc = c + dc[k];
                    if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                    if (g[nr][nc] == 2) continue;
                    if (g[nr][nc] == 1) return steps;
                    g[nr][nc] = 2;
                    q.push({nr, nc});
                }
            }
            ++steps;
        }
        return -1;
    }
};

func shortestBridge(g [][]int) int {
    m, n := len(g), len(g[0])
    dr := []int{-1, 1, 0, 0}
    dc := []int{0, 0, -1, 1}
    q := [][2]int{}
    var dfs func(r, c int)
    dfs = func(r, c int) {
        if r < 0 || r >= m || c < 0 || c >= n || g[r][c] != 1 {
            return
        }
        g[r][c] = 2
        q = append(q, [2]int{r, c})
        for k := 0; k < 4; k++ {
            dfs(r+dr[k], c+dc[k])
        }
    }
    found := false
    for i := 0; i < m && !found; i++ {
        for j := 0; j < n && !found; j++ {
            if g[i][j] == 1 {
                dfs(i, j)
                found = true
            }
        }
    }
    steps := 0
    for len(q) > 0 {
        sz := len(q)
        for ; sz > 0; sz-- {
            r, c := q[0][0], q[0][1]
            q = q[1:]
            for k := 0; k < 4; k++ {
                nr, nc := r+dr[k], c+dc[k]
                if nr < 0 || nr >= m || nc < 0 || nc >= n {
                    continue
                }
                if g[nr][nc] == 2 {
                    continue
                }
                if g[nr][nc] == 1 {
                    return steps
                }
                g[nr][nc] = 2
                q = append(q, [2]int{nr, nc})
            }
        }
        steps++
    }
    return -1
}

from collections import deque
from typing import List

class Solution:
    def shortestBridge(self, g: List[List[int]]) -> int:
        m, n = len(g), len(g[0])
        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        q: deque = deque()

        def dfs(r: int, c: int) -> None:
            if r < 0 or r >= m or c < 0 or c >= n or g[r][c] != 1:
                return
            g[r][c] = 2
            q.append((r, c))
            for dr, dc in dirs:
                dfs(r + dr, c + dc)

        found = False
        for i in range(m):
            if found:
                break
            for j in range(n):
                if g[i][j] == 1:
                    dfs(i, j)
                    found = True
                    break

        steps = 0
        while q:
            for _ in range(len(q)):
                r, c = q.popleft()
                for dr, dc in dirs:
                    nr, nc = r + dr, c + dc
                    if nr < 0 or nr >= m or nc < 0 or nc >= n:
                        continue
                    if g[nr][nc] == 2:
                        continue
                    if g[nr][nc] == 1:
                        return steps
                    g[nr][nc] = 2
                    q.append((nr, nc))
            steps += 1
        return -1

function shortestBridge(g) {
    const m = g.length, n = g[0].length;
    const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    const q = [];
    const dfs = (r, c) => {
        if (r < 0 || r >= m || c < 0 || c >= n || g[r][c] !== 1) return;
        g[r][c] = 2;
        q.push([r, c]);
        for (const [dr, dc] of dirs) dfs(r + dr, c + dc);
    };
    let found = false;
    for (let i = 0; i < m && !found; i++) {
        for (let j = 0; j < n && !found; j++) {
            if (g[i][j] === 1) {
                dfs(i, j);
                found = true;
            }
        }
    }
    let steps = 0;
    let head = 0;
    while (head < q.length) {
        let sz = q.length - head;
        while (sz-- > 0) {
            const [r, c] = q[head++];
            for (const [dr, dc] of dirs) {
                const nr = r + dr, nc = c + dc;
                if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                if (g[nr][nc] === 2) continue;
                if (g[nr][nc] === 1) return steps;
                g[nr][nc] = 2;
                q.push([nr, nc]);
            }
        }
        steps++;
    }
    return -1;
}

class Solution {
    private int m, n;
    private int[][] g;
    private final int[] dr = {-1, 1, 0, 0};
    private final int[] dc = {0, 0, -1, 1};
    private Deque<int[]> q;

    public int shortestBridge(int[][] g) {
        this.g = g;
        m = g.length;
        n = g[0].length;
        q = new ArrayDeque<>();
        boolean found = false;
        for (int i = 0; i < m && !found; i++) {
            for (int j = 0; j < n && !found; j++) {
                if (g[i][j] == 1) {
                    dfs(i, j);
                    found = true;
                }
            }
        }
        int steps = 0;
        while (!q.isEmpty()) {
            int sz = q.size();
            while (sz-- > 0) {
                int[] cell = q.poll();
                int r = cell[0], c = cell[1];
                for (int k = 0; k < 4; k++) {
                    int nr = r + dr[k], nc = c + dc[k];
                    if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                    if (g[nr][nc] == 2) continue;
                    if (g[nr][nc] == 1) return steps;
                    g[nr][nc] = 2;
                    q.offer(new int[]{nr, nc});
                }
            }
            steps++;
        }
        return -1;
    }

    private void dfs(int r, int c) {
        if (r < 0 || r >= m || c < 0 || c >= n || g[r][c] != 1) return;
        g[r][c] = 2;
        q.offer(new int[]{r, c});
        for (int k = 0; k < 4; k++) dfs(r + dr[k], c + dc[k]);
    }
}

function shortestBridge(g: number[][]): number {
    const m = g.length, n = g[0].length;
    const dirs: [number, number][] = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    const q: [number, number][] = [];
    const dfs = (r: number, c: number): void => {
        if (r < 0 || r >= m || c < 0 || c >= n || g[r][c] !== 1) return;
        g[r][c] = 2;
        q.push([r, c]);
        for (const [dr, dc] of dirs) dfs(r + dr, c + dc);
    };
    let found = false;
    for (let i = 0; i < m && !found; i++) {
        for (let j = 0; j < n && !found; j++) {
            if (g[i][j] === 1) {
                dfs(i, j);
                found = true;
            }
        }
    }
    let steps = 0;
    let head = 0;
    while (head < q.length) {
        let sz = q.length - head;
        while (sz-- > 0) {
            const [r, c] = q[head++];
            for (const [dr, dc] of dirs) {
                const nr = r + dr, nc = c + dc;
                if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                if (g[nr][nc] === 2) continue;
                if (g[nr][nc] === 1) return steps;
                g[nr][nc] = 2;
                q.push([nr, nc]);
            }
        }
        steps++;
    }
    return -1;
}

Editorial#

The two-phase trick — flood one island, then BFS the gap — is the standard “shortest path between two regions” recipe. Multi-source BFS from the first island ensures the very first frontier intersection with the second island is the minimum bridge.

Complexity#

Time: O(n^2).
Space: O(n^2).

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#