934. Shortest Bridge

Problem Description

You are given an n x n binary matrix grid where 1 represents land and 0 represents water.

An island is a 4-directionally connected group of 1's not connected to any other 1's. There are exactly two islands in grid.

You may change 0's to 1's to connect the two islands to form one island.

Return the smallest number of 0's you must flip to connect 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:

• n == grid.length == grid[i].length
• 2 <= n <= 100
• grid[i][j] is either 0 or 1.
• There are exactly two islands in grid.

Python Solution

class Solution:
    def shortestBridge(self, grid: List[List[int]]) -> int:
        n = len(grid)
        # Find first island
        def find_first_island():
            for i in range(n):
                for j in range(n):
                    if grid[i][j] == 1:
                        return i, j
            return -1, -1
        
        # DFS to mark first island
        def mark_island(i, j):
            if i < 0 or i >= n or j < 0 or j >= n or grid[i][j] != 1:
                return
            grid[i][j] = 2
            for di, dj in [(0,1), (1,0), (0,-1), (-1,0)]:
                mark_island(i + di, j + dj)
        
        # BFS to find shortest bridge
        def find_bridge():
            queue = []
            for i in range(n):
                for j in range(n):
                    if grid[i][j] == 2:
                        queue.append((i, j, 0))
            
            visited = set()
            while queue:
                i, j, dist = queue.pop(0)
                if (i, j) in visited:
                    continue
                visited.add((i, j))
                
                if grid[i][j] == 1:
                    return dist - 1
                
                for di, dj in [(0,1), (1,0), (0,-1), (-1,0)]:
                    ni, nj = i + di, j + dj
                    if 0 <= ni < n and 0 <= nj < n and (ni, nj) not in visited:
                        queue.append((ni, nj, dist + 1))
            return 0
        
        # Main logic
        i, j = find_first_island()
        mark_island(i, j)
        return find_bridge()

Java Solution

class Solution {
    private int n;
    private int[][] grid;
    
    public int shortestBridge(int[][] grid) {
        this.grid = grid;
        this.n = grid.length;
        
        // Find first island
        int[] first = findFirstIsland();
        if (first == null) return 0;
        
        // Mark first island
        markIsland(first[0], first[1]);
        
        // Find shortest bridge
        return findBridge();
    }
    
    private int[] findFirstIsland() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    return new int[]{i, j};
                }
            }
        }
        return null;
    }
    
    private void markIsland(int i, int j) {
        if (i < 0 || i >= n || j < 0 || j >= n || grid[i][j] != 1) {
            return;
        }
        grid[i][j] = 2;
        markIsland(i + 1, j);
        markIsland(i - 1, j);
        markIsland(i, j + 1);
        markIsland(i, j - 1);
    }
    
    private int findBridge() {
        Queue queue = new LinkedList<>();
        boolean[][] visited = new boolean[n][n];
        
        // Add all cells of first island to queue
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) {
                    queue.offer(new int[]{i, j, 0});
                }
            }
        }
        
        int[][] dirs = {{0,1}, {1,0}, {0,-1}, {-1,0}};
        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int i = curr[0], j = curr[1], dist = curr[2];
            
            if (visited[i][j]) continue;
            visited[i][j] = true;
            
            if (grid[i][j] == 1) {
                return dist - 1;
            }
            
            for (int[] dir : dirs) {
                int ni = i + dir[0], nj = j + dir[1];
                if (ni >= 0 && ni < n && nj >= 0 && nj < n && !visited[ni][nj]) {
                    queue.offer(new int[]{ni, nj, dist + 1});
                }
            }
        }
        return 0;
    }
}

C++ Solution

class Solution {
private:
    int n;
    vector> grid;
    
    pair findFirstIsland() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    return {i, j};
                }
            }
        }
        return {-1, -1};
    }
    
    void markIsland(int i, int j) {
        if (i < 0 || i >= n || j < 0 || j >= n || grid[i][j] != 1) {
            return;
        }
        grid[i][j] = 2;
        markIsland(i + 1, j);
        markIsland(i - 1, j);
        markIsland(i, j + 1);
        markIsland(i, j - 1);
    }
    
    int findBridge() {
        queue> q;
        vector> visited(n, vector(n, false));
        
        // Add all cells of first island to queue
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) {
                    q.push({i, j, 0});
                }
            }
        }
        
        vector> dirs = {{0,1}, {1,0}, {0,-1}, {-1,0}};
        while (!q.empty()) {
            auto curr = q.front();
            q.pop();
            int i = curr[0], j = curr[1], dist = curr[2];
            
            if (visited[i][j]) continue;
            visited[i][j] = true;
            
            if (grid[i][j] == 1) {
                return dist - 1;
            }
            
            for (auto& dir : dirs) {
                int ni = i + dir[0], nj = j + dir[1];
                if (ni >= 0 && ni < n && nj >= 0 && nj < n && !visited[ni][nj]) {
                    q.push({ni, nj, dist + 1});
                }
            }
        }
        return 0;
    }
    
public:
    int shortestBridge(vector>& grid) {
        this->grid = grid;
        this->n = grid.size();
        
        auto first = findFirstIsland();
        if (first.first == -1) return 0;
        
        markIsland(first.first, first.second);
        return findBridge();
    }
};

JavaScript Solution

/**
 * @param {number[][]} grid
 * @return {number}
 */
var shortestBridge = function(grid) {
    const n = grid.length;
    
    function findFirstIsland() {
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                if (grid[i][j] === 1) {
                    return [i, j];
                }
            }
        }
        return [-1, -1];
    }
    
    function markIsland(i, j) {
        if (i < 0 || i >= n || j < 0 || j >= n || grid[i][j] !== 1) {
            return;
        }
        grid[i][j] = 2;
        markIsland(i + 1, j);
        markIsland(i - 1, j);
        markIsland(i, j + 1);
        markIsland(i, j - 1);
    }
    
    function findBridge() {
        const queue = [];
        const visited = Array(n).fill().map(() => Array(n).fill(false));
        
        // Add all cells of first island to queue
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                if (grid[i][j] === 2) {
                    queue.push([i, j, 0]);
                }
            }
        }
        
        const dirs = [[0,1], [1,0], [0,-1], [-1,0]];
        while (queue.length > 0) {
            const [i, j, dist] = queue.shift();
            
            if (visited[i][j]) continue;
            visited[i][j] = true;
            
            if (grid[i][j] === 1) {
                return dist - 1;
            }
            
            for (const [di, dj] of dirs) {
                const ni = i + di, nj = j + dj;
                if (ni >= 0 && ni < n && nj >= 0 && nj < n && !visited[ni][nj]) {
                    queue.push([ni, nj, dist + 1]);
                }
            }
        }
        return 0;
    }
    
    const [i, j] = findFirstIsland();
    if (i === -1) return 0;
    
    markIsland(i, j);
    return findBridge();
};

C# Solution

public class Solution {
    private int n;
    private int[][] grid;
    
    public int ShortestBridge(int[][] grid) {
        this.grid = grid;
        this.n = grid.Length;
        
        var first = FindFirstIsland();
        if (first == null) return 0;
        
        MarkIsland(first[0], first[1]);
        return FindBridge();
    }
    
    private int[] FindFirstIsland() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    return new int[] { i, j };
                }
            }
        }
        return null;
    }
    
    private void MarkIsland(int i, int j) {
        if (i < 0 || i >= n || j < 0 || j >= n || grid[i][j] != 1) {
            return;
        }
        grid[i][j] = 2;
        MarkIsland(i + 1, j);
        MarkIsland(i - 1, j);
        MarkIsland(i, j + 1);
        MarkIsland(i, j - 1);
    }
    
    private int FindBridge() {
        var queue = new Queue<(int i, int j, int dist)>();
        var visited = new bool[n, n];
        
        // Add all cells of first island to queue
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) {
                    queue.Enqueue((i, j, 0));
                }
            }
        }
        
        var dirs = new (int di, int dj)[] { (0,1), (1,0), (0,-1), (-1,0) };
        while (queue.Count > 0) {
            var (i, j, dist) = queue.Dequeue();
            
            if (visited[i,j]) continue;
            visited[i,j] = true;
            
            if (grid[i][j] == 1) {
                return dist - 1;
            }
            
            foreach (var (di, dj) in dirs) {
                int ni = i + di, nj = j + dj;
                if (ni >= 0 && ni < n && nj >= 0 && nj < n && !visited[ni,nj]) {
                    queue.Enqueue((ni, nj, dist + 1));
                }
            }
        }
        return 0;
    }
}