Shortest Bridge

medium array dfs bfs matrix

Problem

Given a binary grid with exactly two islands (connected groups of 1s), return the smallest number of 0s to flip to 1s to connect them.

Inputgrid = [[0,1,0],[0,0,0],[0,0,1]]

Output2

Flood-fill one island (mark = 2), then BFS outward in layers; depth on first hit is the bridge length.

grid (rows separated by ';')

from collections import deque
def shortestBridge(grid):
    n = len(grid)
    q = deque()
    def dfs(r, c):
        if r < 0 or r >= n or c < 0 or c >= n or grid[r][c] != 1: return
        grid[r][c] = 2
        q.append((r, c, 0))
        for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
            dfs(r + dr, c + dc)
    found = False
    for r in range(n):
        for c in range(n):
            if grid[r][c] == 1 and not found:
                dfs(r, c); found = True
                break
        if found: break
    while q:
        r, c, d = q.popleft()
        for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n:
                if grid[nr][nc] == 1: return d
                if grid[nr][nc] == 0:
                    grid[nr][nc] = 2
                    q.append((nr, nc, d + 1))
    return -1

function shortestBridge(grid) {
  const n = grid.length;
  const q = [];
  function dfs(r, c) {
    if (r < 0 || r >= n || c < 0 || c >= n || grid[r][c] !== 1) return;
    grid[r][c] = 2;
    q.push([r, c, 0]);
    dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1);
  }
  outer: for (let r = 0; r < n; r++) for (let c = 0; c < n; c++) if (grid[r][c] === 1) { dfs(r, c); break outer; }
  let head = 0;
  while (head < q.length) {
    const [r, c, d] = q[head++];
    for (const [dr, dc] of [[1,0],[-1,0],[0,1],[0,-1]]) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
      if (grid[nr][nc] === 1) return d;
      if (grid[nr][nc] === 0) { grid[nr][nc] = 2; q.push([nr, nc, d + 1]); }
    }
  }
  return -1;
}

class Solution {
    int n;
    Deque<int[]> q = new ArrayDeque<>();
    public int shortestBridge(int[][] grid) {
        n = grid.length;
        outer: for (int r = 0; r < n; r++) for (int c = 0; c < n; c++)
            if (grid[r][c] == 1) { dfs(grid, r, c); break outer; }
        int[][] D = { {1,0},{-1,0},{0,1},{0,-1} };
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int r = cur[0], c = cur[1], d = cur[2];
            for (int[] dd : D) {
                int nr = r + dd[0], nc = c + dd[1];
                if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
                if (grid[nr][nc] == 1) return d;
                if (grid[nr][nc] == 0) { grid[nr][nc] = 2; q.offer(new int[]{nr, nc, d + 1}); }
            }
        }
        return -1;
    }
    void dfs(int[][] g, int r, int c) {
        if (r < 0 || r >= n || c < 0 || c >= n || g[r][c] != 1) return;
        g[r][c] = 2; q.offer(new int[]{r, c, 0});
        dfs(g, r + 1, c); dfs(g, r - 1, c); dfs(g, r, c + 1); dfs(g, r, c - 1);
    }
}

int shortestBridge(vector<vector<int>>& grid) {
    int n = (int)grid.size();
    queue<tuple<int, int, int>> q;
    function<void(int, int)> dfs = [&](int r, int c) {
        if (r < 0 || r >= n || c < 0 || c >= n || grid[r][c] != 1) return;
        grid[r][c] = 2; q.push({r, c, 0});
        dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1);
    };
    bool found = false;
    for (int r = 0; r < n && !found; r++) for (int c = 0; c < n && !found; c++)
        if (grid[r][c] == 1) { dfs(r, c); found = true; }
    int D[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
    while (!q.empty()) {
        auto [r, c, d] = q.front(); q.pop();
        for (auto& dd : D) {
            int nr = r + dd[0], nc = c + dd[1];
            if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
            if (grid[nr][nc] == 1) return d;
            if (grid[nr][nc] == 0) { grid[nr][nc] = 2; q.push({nr, nc, d + 1}); }
        }
    }
    return -1;
}

Explanation

We want the fewest water cells to flip to connect two islands. The idea is two phases: first identify all of island A, then expand outward from the whole island at once until we touch island B. The distance traveled is the bridge length.

Phase 1 is a DFS flood-fill: starting from the first 1 we find, we mark every connected land cell as 2 so we can tell island A apart, and we push each of those cells into the queue q with distance 0.

Phase 2 is a multi-source BFS from every cell of island A simultaneously. We step into neighboring water (0), mark it 2, and record one more unit of distance. The instant a step lands on a cell still equal to 1, we've reached island B, and the current depth d is the answer.

Example: [[0,1,0],[0,0,0],[0,0,1]]. Island A is the lone 1 at top. BFS expands ring by ring through the water; it must cross 2 water cells before touching the bottom island, so the answer is 2.

Starting BFS from every A-cell at once guarantees the first time we hit B, we found the shortest possible gap between the two islands.

Time: O(R · C) Space: O(R · C)