Problem Explanation

Given a 2D binary array with two disconnected islands of 1s, the aim is to connect these islands by flipping the minimum number of 0s to 1s. Here, an 'island' is a group of adjacently connected 1s.

Consider an example where the binary array is as follows:

1
2
31 1
40 0
51 1

Here, we have two islands. The smallest number of 0s that need to be flipped is 2. By flipping the two zeros in the middle row, the two islands can be connected.

Approach

This problem can be solved via Depth-First Search (DFS) and Breadth-First Search (BFS) algorithms. First, we identify one of the islands and mark it distinctly (e.g., as 2s). We then utilize a BFS-based approach to expand this island by marking the adjacent 0s with increasing integers. When we encounter a cell marked as 1 (representing the second island), we stop. The minimum number of 0s flipped is the value of the cell where we stop minus 2. The minus 2 is because we started marking cells (expanding from island 1) using the integer 3.

Walkthrough

Consider for instance the following grid:

1
2
3Input: [[1,1,1,0,0],[1,0,0,0,1],[1,0,1,0,0]]

First, one of the islands is identified and marked with 2. After this step, the grid appears like:

1
2
3[[2,2,2,0,0],
4 [2,0,0,0,1],
5 [2,0,1,0,0]]

Then, applying a BFS approach, we start expanding from the marked island by changing the neighboring 0s to 3s, 4s, and so on until we reach the other island. After these steps, the grid appears like:

1
2
3[[2,2,2,3,3],
4 [2,3,3,3,1],
5 [2,3,1,4,4]]

Now, we have reached the second island (cell marked with 1). So, we stop expanding. The minimum number of 0s flipped is the cell where we stop minus 2, therefore, the minimum number of 0s flipped is 3 - 2 = 1.

Java Solution

1
2java
3public class Solution {
4    public int shortestBridge(int[][] A) {
5        int rows = A.length, cols = A[0].length;
6        boolean[][] visited = new boolean[rows][cols];
7        Deque<int[]> queue = new ArrayDeque<>();
8        boolean found = false;
9        
10        for (int i = 0; i < rows; i++) {
11            if (found) {
12                break;
13            }
14            for (int j = 0; j < cols; j++) {
15                if (A[i][j] == 1) {
16                    dfs(A, visited, queue, i, j);
17                    found = true;
18                    break;
19                }
20            }
21        }
22        
23        int level = 0;
24        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
25        while (!queue.isEmpty()) {
26            int size = queue.size();
27            while (size-- > 0) {
28                int[] cur = queue.poll();
29                for (int[] dir : directions) {
30                    int x = cur[0] + dir[0];
31                    int y = cur[1] + dir[1];
32                    if (x < 0 || y < 0 || x >= rows || y >= cols || visited[x][y]) {
33                        continue;
34                    }
35                    if (A[x][y] == 1) {
36                        return level;
37                    }
38                    queue.offer(new int[]{x, y});
39                    visited[x][y] = true;
40                }
41            }
42            level++;
43        }
44        return -1;
45    }
46    
47    private void dfs(int[][] A, boolean[][] visited, Deque<int[]> queue, int i, int j) {
48        if (i < 0 || j < 0 || i >= A.length || j >= A[0].length || visited[i][j] || A[i][j] == 0) {
49            return;
50        }
51        visited[i][j] = true;
52        queue.offer(new int[]{i, j});
53        dfs(A, visited, queue, i - 1, j);
54        dfs(A, visited, queue, i + 1, j);
55        dfs(A, visited, queue, i, j - 1);
56        dfs(A, visited, queue, i, j + 1);
57    }
58}

This solution implements both DFS and BFS. DFS identifies the first island and BFS is used to reach the second island with a minimum number of steps. The function 'dfs' is used to explore the first island cells and add them to the BFS queue. This solution performs efficiently with a time complexity of O(rc), where r and c are row and column counts respectively. The space complexity is O(rc) as well due to the BFS queue and the visited map.

Please implement the solution in other languages as per your requirement.# Python Solution

Here is a python solution for this problem. In Python, we will be using the built-in list comprehension and traversal functions to write cleaner and more efficient code.

1
2python
3def shortestBridge(A):
4    row, col = len(A), len(A[0])
5    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
6    
7    def dfs(i, j):
8        if i<0 or j<0 or i>=row or j>=col or A[i][j] != 1: return 
9        A[i][j] = -1
10        queue.append((i,j))
11        for x, y in directions:
12            dfs(i+x, j+y)
13            
14    def bfs():
15        level = 0
16        while queue:
17            for _ in range(len(queue)):
18                x, y = queue.pop(0)
19                for dx, dy in directions:
20                    nx, ny = x+dx, y+dy
21                    if nx<0 or ny<0 or nx>=row or ny>=col or A[nx][ny]==-1: continue 
22                    if A[nx][ny] == 1: return level
23                    A[nx][ny] = -1
24                    queue.append((nx,ny))
25            level += 1
26            
27    queue = []
28    breakFlag = False
29    for i in range(row):
30        if breakFlag:
31            break
32        for j in range(col):
33            if A[i][j] == 1:
34                dfs(i,j)
35                breakFlag = True
36                break
37    return bfs()

The way this solution works is identical to the Java solution above. We first use Depth-First Search (DFS) to identify one of the islands and then Breadth-First Search (BFS) to expand the island until we find the shortest path to the other island.

JavaScript Solution

A similar solution can also be implemented in JavaScript. JavaScript arrays have built-in methods such as push and shift that can be used to simulate a queue.

1
2javascript
3function shortestBridge(A) {
4            const [queue, set] = dfs(A), DIR = [[0, 1], [0, -1], [1, 0], [-1, 0]];
5            let bridge = 0;
6        
7            while (queue.length) {
8                const nextRound = [];
9                while (queue.length) {
10                    const [px, py] = queue.shift();
11                    for (const [dx, dy] of DIR) {
12                        const x = px + dx, y = py + dy;
13                        if (x < 0 || x >= A.length || y < 0 || y >= A[0].length || set.has(x + '/' + y)) continue;
14                        if (A[x][y] === 1) return bridge;
15                        nextRound.push([x,y]);
16                        set.add(x + '/' + y);
17                    }
18                }
19                queue.push(...nextRound);
20                bridge++;
21            }
22        
23            function dfs(A) {
24                const stack = [[A.findIndex(row => row.includes(1)), A[0].findIndex(pixel => pixel === 1)]], set = new Set(), queue = [];
25                while (stack.length) {
26                    const [x, y] = stack.pop();
27                    A[x][y] = -1;
28                    queue.push([x, y]);
29                    set.add(x + '/' + y);
30                    for (const [dx, dy] of DIR) {
31                        const px = x + dx, py = y + dy;
32                        if (px < 0 || py < 0 || px >= A.length || py >= A[0].length || A[px][py] === 0 || set.has(px + '/' + py)) continue;
33                        stack.push([px, py]);
34                    }
35                }
36                return [queue, set];
37            }
38        }

The way the JavaScript solution works is it first applies DFS to find any pixel of the first island and then, it uses BFS to gradually expand the first island region. When, the BFS hits the second island, the function returns the 'bridge' variable which keeps track of the layers of BFS.

Please note that Python and JavaScript solutions also have a time complexity of O(rc) and space complexity O(rc), same as Java solution.