934. Shortest Bridge - Leetcode Solution

Code Implementation

from collections import deque

class Solution:
    def shortestBridge(self, grid):
        n, m = len(grid), len(grid[0])
        visited = [[False]*m for _ in range(n)]
        dirs = [(-1,0), (1,0), (0,-1), (0,1)]
        queue = deque()
        
        def in_bounds(x, y):
            return 0 <= x < n and 0 <= y < m
        
        # 1. Find and mark the first island
        def dfs(x, y):
            if not in_bounds(x, y) or visited[x][y] or grid[x][y] == 0:
                return
            visited[x][y] = True
            queue.append((x, y))
            for dx, dy in dirs:
                dfs(x+dx, y+dy)
        
        found = False
        for i in range(n):
            if found:
                break
            for j in range(m):
                if grid[i][j] == 1:
                    dfs(i, j)
                    found = True
                    break
        
        # 2. BFS to expand outward and find the second island
        steps = 0
        while queue:
            for _ in range(len(queue)):
                x, y = queue.popleft()
                for dx, dy in dirs:
                    nx, ny = x+dx, y+dy
                    if in_bounds(nx, ny) and not visited[nx][ny]:
                        if grid[nx][ny] == 1:
                            return steps
                        visited[nx][ny] = True
                        queue.append((nx, ny))
            steps += 1

#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    int shortestBridge(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<bool>> visited(n, vector<bool>(m, false));
        queue<pair<int,int>> q;
        vector<pair<int,int>> dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};
        
        auto in_bounds = [&](int x, int y) {
            return x >= 0 && x < n && y >= 0 && y < m;
        };
        
        function<void(int,int)> dfs = [&](int x, int y) {
            if (!in_bounds(x, y) || visited[x][y] || grid[x][y] == 0) return;
            visited[x][y] = true;
            q.push({x, y});
            for (auto d : dirs) dfs(x+d.first, y+d.second);
        };
        
        bool found = false;
        for (int i = 0; i < n && !found; ++i) {
            for (int j = 0; j < m && !found; ++j) {
                if (grid[i][j] == 1) {
                    dfs(i, j);
                    found = true;
                }
            }
        }
        
        int steps = 0;
        while (!q.empty()) {
            int sz = q.size();
            while (sz--) {
                auto [x, y] = q.front(); q.pop();
                for (auto d : dirs) {
                    int nx = x + d.first, ny = y + d.second;
                    if (in_bounds(nx, ny) && !visited[nx][ny]) {
                        if (grid[nx][ny] == 1) return steps;
                        visited[nx][ny] = true;
                        q.push({nx, ny});
                    }
                }
            }
            ++steps;
        }
        return -1;
    }
};

import java.util.*;

class Solution {
    int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
    int n, m;
    boolean[][] visited;
    Queue<int[]> queue = new LinkedList<>();

    public int shortestBridge(int[][] grid) {
        n = grid.length;
        m = grid[0].length;
        visited = new boolean[n][m];
        
        // 1. Find and mark the first island
        boolean found = false;
        for (int i = 0; i < n && !found; ++i) {
            for (int j = 0; j < m && !found; ++j) {
                if (grid[i][j] == 1) {
                    dfs(grid, i, j);
                    found = true;
                }
            }
        }
        
        // 2. BFS to find shortest bridge
        int steps = 0;
        while (!queue.isEmpty()) {
            int sz = queue.size();
            for (int i = 0; i < sz; ++i) {
                int[] cell = queue.poll();
                for (int[] d : dirs) {
                    int nx = cell[0] + d[0], ny = cell[1] + d[1];
                    if (inBounds(nx, ny) && !visited[nx][ny]) {
                        if (grid[nx][ny] == 1) return steps;
                        visited[nx][ny] = true;
                        queue.offer(new int[]{nx, ny});
                    }
                }
            }
            steps++;
        }
        return -1;
    }
    
    void dfs(int[][] grid, int x, int y) {
        if (!inBounds(x, y) || visited[x][y] || grid[x][y] == 0) return;
        visited[x][y] = true;
        queue.offer(new int[]{x, y});
        for (int[] d : dirs) dfs(grid, x+d[0], y+d[1]);
    }
    
    boolean inBounds(int x, int y) {
        return x >= 0 && x < n && y >= 0 && y < m;
    }
}

var shortestBridge = function(grid) {
    const n = grid.length, m = grid[0].length;
    const visited = Array.from({length: n}, () => Array(m).fill(false));
    const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
    const queue = [];
    
    function inBounds(x, y) {
        return x >= 0 && x < n && y >= 0 && y < m;
    }
    
    function dfs(x, y) {
        if (!inBounds(x, y) || visited[x][y] || grid[x][y] === 0) return;
        visited[x][y] = true;
        queue.push([x, y]);
        for (const [dx, dy] of dirs) dfs(x+dx, y+dy);
    }
    
    let found = false;
    for (let i = 0; i < n && !found; ++i) {
        for (let j = 0; j < m && !found; ++j) {
            if (grid[i][j] === 1) {
                dfs(i, j);
                found = true;
            }
        }
    }
    
    let steps = 0;
    while (queue.length) {
        let sz = queue.length;
        while (sz--) {
            const [x, y] = queue.shift();
            for (const [dx, dy] of dirs) {
                const nx = x + dx, ny = y + dy;
                if (inBounds(nx, ny) && !visited[nx][ny]) {
                    if (grid[nx][ny] === 1) return steps;
                    visited[nx][ny] = true;
                    queue.push([nx, ny]);
                }
            }
        }
        steps++;
    }
    return -1;
};

Problem Description

You are given a 2D binary array grid where grid[i][j] is either 0 (water) or 1 (land). The grid contains exactly two separate islands (groups of 1s connected 4-directionally). Your goal is to build a "bridge" (by flipping water cells to land) to connect the two islands, such that the number of 0s you must flip is minimized.

You may only flip 0s to 1s (not vice versa).
There is exactly one valid solution.
Do not reuse elements: you cannot flip the same cell twice.
Return the minimal number of 0s that need to be flipped to connect the two islands.

Thought Process

At first glance, connecting two islands in a grid might seem to require checking all possible paths between them. This brute-force approach would be inefficient, especially for large grids. Instead, we can use a more systematic method:

First, identify and mark all cells of one island. This helps us distinguish between the two islands and provides a starting point for searching.
Next, we want to find the shortest path (i.e., minimal number of water cells to flip) from this first island to the second. This is a classic "shortest path in unweighted grid" problem, solvable efficiently with Breadth-First Search (BFS).
By expanding outwards from all cells of the first island simultaneously (multi-source BFS), we guarantee that the first time we reach the second island, we've found the shortest bridge.
This approach is much faster and more elegant than brute-forcing all possible bridges.

Solution Approach

Step 1: Find and Mark the First Island
- Loop through the grid to find the first cell with value 1.
- Use Depth-First Search (DFS) from this cell to mark all connected 1s (the first island) as visited.
- While marking, add each island cell's coordinates to a queue. This queue will be the starting point for BFS.
Step 2: Expand Outwards with BFS
- From all marked cells (the first island), perform BFS. For each expansion step, increment a step counter.
- For each water cell (0) reached, mark it as visited and add it to the queue for the next layer of BFS.
- If you reach a cell with value 1 that hasn't been visited yet, you've reached the second island. Return the current step count as the answer.
Design Choices Justified:
- DFS for marking: Ensures all cells of the first island are found efficiently.
- BFS for shortest path: Guarantees the minimal number of flips, since BFS explores all possible bridges of length 1, then 2, etc.
- Visited tracking: Prevents revisiting the same cell, avoiding infinite loops and redundant work.

Example Walkthrough

Let's consider the following input grid:

    0 1 0
    0 0 0
    0 0 1

Find and mark the first island:
- We find grid[0][1] is 1. Using DFS, we mark it visited and add to the queue: queue = [(0,1)].
BFS expansion:
- Step 0: From (0,1), visit its neighbors:
  - (1,1) is 0, mark as visited and add to queue.
  - (0,0) and (0,2) are 0, mark as visited and add to queue.
- Step 1: From all newly added cells, expand again:
  - (1,1): neighbors include (2,1) and (1,0), both 0, add to queue.
  - (0,0): neighbor (1,0) already added.
  - (0,2): neighbor (1,2) is 0, add to queue.
- Step 2: From (2,1), (1,0), (1,2):
  - (2,1): neighbor (2,2) is 1 (second island) — we've connected!
The minimal number of 0s to flip is 2.

Time and Space Complexity

Brute-force approach:
- Would involve checking all pairs of points between two islands, and for each, finding the path, resulting in at least O(N^4) time for an N x N grid.
Optimized approach (DFS + BFS):
- DFS marking: Each cell is visited once, O(N^2).
- BFS expansion: Each cell is added to the queue at most once, O(N^2).
- Total time complexity: O(N^2).
- Space complexity: O(N^2) for visited array and queue.

Summary

The Shortest Bridge problem is elegantly solved by first identifying one island using DFS, then expanding outward with BFS to find the shortest path to the second island. This approach leverages classic graph techniques to guarantee the minimal number of flips, with clear time and space efficiency. The key insight is to treat the problem as a multi-source shortest path search, ensuring that as soon as the second island is reached, the minimal solution has been found.

AlgoMap.io

Want Help Cracking FAANG?