934. Shortest Bridge

MediumDepth-First SearchBreadth-First SearchArrayMatrix

Problem Description

The problem presents us with an n x n binary matrix grid, which contains 1s and 0s where 1 represents land and 0 represents water. There are exactly two separate areas (islands) in this grid, which are represented by connected groups of 1s. An important detail is that these connections are only in the four cardinal directions (up, down, left, right). The challenge is to determine the minimum number of 0s (water) that we must convert into 1s (land) to connect the two islands into a single landmass. To summarize, the goal is to transform the smallest possible number of 0s into 1s such that the two islands become directly connected.

Flowchart Walkthrough

Let's analyze Leetcode 934. Shortest Bridge using the algorithm flowchart as a guide. Here's a step-by-step walkthrough based on the Flowchart found here:

Is it a graph?

Yes: The 2D grid in this problem can be represented as a graph where each cell is a node, and adjacent cells (horizontally or vertically) are connected if they are land cells.

Is it a tree?

No: Although it's based on a grid structure, the multiple connections mean it's not a tree.

Is the problem related to directed acyclic graphs (DAGs)?

No: The problem involves finding the shortest bridge (minimum distance) between two islands, not about traversing directed acyclic graphs.

Is the problem related to shortest paths?

Yes: The task requires finding the shortest path between two distinct islands.

Does the problem involve connectivity?

Yes: Connectivity is key as we are trying to connect two already existing islands with the shortest path.

Is the graph weighted?

No: The distances involved in connecting two islands in the grid are uniform (simply counting steps), implying an unweighted scenario.

Conclusion: While the flowchart suggests using BFS for this unweighted connectivity problem (as both BFS and DFS can be suited for finding shortest paths in unweighted graphs), using DFS to initially identify the two distinct islands followed by BFS to calculate the shortest bridge makes efficient use of the Depth-First Search pattern in the initial enumeration phase. DFS is optimal here for identifying and marking the two separate islands comprehensively before applying BFS for distance calculation.

Intuition

The solution to this problem uses both Depth-First Search (DFS) and Breadth-First Search (BFS) algorithms. The intuition behind the solution is to treat the problem as a two-step process:

Identify and Separate the Two Islands: First, we find one of the islands using a DFS algorithm to look for the first land cell (marked by a 1). Once we find it, we perform a DFS starting from that cell to mark all connected land cells as part of the same island. For clarity, we mark these cells with a 2. At the end of this step, we will have isolated one island, and the other will remain marked with 1s.
Find the Shortest Path to the Other Island: After marking one island, we use a BFS algorithm to expand outward from the marked island. We look at all the cells at the current 'frontier', and for each, we inspect their neighboring cells. If we encounter a cell with a 0, we convert it into a 2 and add it to the queue for the next layer of expansion. This expansion simulates the process of 'building a bridge' to the other island. If we encounter a 1 during this expansion, it means we have reached the second island, and the current distance (or the number of 0s converted to 2s) represents the minimal bridge length required to connect the islands. The BFS finishes once the connection is made.

The key aspect of this approach is to expand uniformly from the entire frontier of the marked island instead of from a single point. This ensures that the shortest path will be found, as BFS guarantees the shortest path in an unweighted graph, which in this case is represented by the grid with 0s and 1s.

Learn more about Depth-First Search and Breadth-First Search patterns.

Solution Approach

The implementation of the solution can be broken down into two primary components: identifying one of the islands (isolation step) using DFS, and then finding the shortest path to the other island (connection step) using BFS.

Isolation Step (DFS): We start by initializing a variable dirs to represent the four cardinal directions for traversal. We then find a starting point, which is the first 1 encountered in the grid, indicating a part of the first island. From this initial cell, we perform a DFS. In the DFS function, we mark the current cell with 2 to distinguish it from the other unvisited land cells (1) and water (0). For every cell marked as 2, we continue the DFS for each of its unvisited land neighbors by recursively calling the DFS function. We also add the cells to a queue q, which will be used later for the BFS expansion.
Connection Step (BFS): After isolating one island and marking it with 2s, we use BFS to 'build the bridge' to the second island. We initialize a variable ans to keep track of the number of flips required. During the BFS, we dequeue cells from q and explore their neighbors in all four directions. We have three cases for each neighbor:
- If the cell is water (0), we flip it to (2) to indicate it is now part of the bridge and add it to the queue for further exploration.
- If the cell is a part of the unvisited island (1), we have reached the second island, and we return the ans variable because we found the minimal number of flips to connect the two islands.
- If the cell is already included in the bridge or is a part of the isolated island (2), we ignore it and continue.

The BFS continues in this manner, layer by layer, in a while loop. Each loop iteration corresponds to expanding the 'frontier' by one more step. This ensures that when we do encounter a cell belonging to the second island, we have taken the minimal number of steps to get there. When encounter occurs, the value of ans represents the smallest number of 0s that we have flipped, and this value is returned as the final answer.

In summary, the DFS is used to isolate and mark one island, and the BFS is used to calculate the minimal distance to the other island by simulating the process of building a bridge one cell at a time.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small 5x5 binary matrix grid as an example to walk through the solution approach.

Let's apply both DFS and BFS algorithms to solve it following the steps described above.

Step 1: Isolation Step (DFS)

Begin the DFS by scanning for "1" from the top-left corner. The first "1" is encountered at grid[0][1].
Initiate DFS from this cell, marking all connected "1s" as "2s", so that cell's part of the first island are differentiated.

Updated grid after DFS:

Now, all the cells from the first island are marked as 2, and we create a queue q with these cells, which will be (0,1) and (1,1).

Step 2: Connection Step (BFS)

Begin a BFS starting from the queue of the first island's perimeter—the 2s.
Start expanding layer by layer. Initially, ans is set to 0, representing the number of flips (or bridge's length) required so far.

First iteration of BFS (adding surrounding 0s of starting island to the queue):

0 2 2 0 0
0 2 2 0 0
0 0 0 1 1
0 0 0 0 0
0 0 0 0 1
ans = 1 (since we transformed one '0' to '2')

Second iteration of BFS (continuing to expand):

Third iteration of BFS (the frontier now touches the second island):

The BFS stops here as the expanding cells meet the second island, which is still marked with 1s. The minimum number of flips is 2, as that's the BFS depth when the connection with the second island was made.

So the minimum number of 0s that must be converted to 1s to connect the two islands in this example is 2.

Solution Implementation

1from collections import deque
2
3class Solution:
4    def shortestBridge(self, grid):
5        # Depth-first search function to mark the first island
6        def dfs(i, j):
7            queue.append((i, j))
8            grid[i][j] = 2
9            for k in range(4):
10                x, y = i + directions[k], j + directions[k+1]
11                if 0 <= x < size and 0 <= y < size and grid[x][y] == 1:
12                    dfs(x, y)
13      
14        size = len(grid)
15        # Directions for exploring neighboring cells (right, down, left, up)
16        directions = [0, 1, 0, -1, 0]
17        queue = deque()
18      
19        # Find the first 1 in the grid to start the DFS
20        start_i, start_j = next((i, j) for i in range(size) for j in range(size) if grid[i][j] == 1)
21      
22        # Run DFS to find one island and mark it as 2
23        dfs(start_i, start_j)
24      
25        steps = 0  # Number of steps required to connect the two islands
26        # BFS to expand the first island
27        while True:
28            for _ in range(len(queue)):
29                i, j = queue.popleft()
30                for k in range(4):
31                    x, y = i + directions[k], j + directions[k+1]
32                    if 0 <= x < size and 0 <= y < size:
33                        # When we find the second island, return the number of steps
34                        if grid[x][y] == 1:
35                            return steps
36                        # If water is found, mark it as part of the first island and add to the queue
37                        if grid[x][y] == 0:
38                            grid[x][y] = 2
39                            queue.append((x, y))
40            steps += 1
41

1class Solution {
2    // Movement directions (up, right, down, left)
3    private int[] directions = {-1, 0, 1, 0, -1};
4  
5    // Queue to keep track of the expansion of the island
6    private Deque<int[]> queue = new ArrayDeque<>();
7  
8    // The input grid representation of islands
9    private int[][] grid;
10  
11    // Size of the grid
12    private int size;
13  
14    public int shortestBridge(int[][] grid) {
15        this.grid = grid;
16        size = grid.length;
17      
18        // Find the first island and perform DFS to mark it
19        boolean foundFirstIsland = false;
20        for (int i = 0; i < size && !foundFirstIsland; ++i) {
21            for (int j = 0; j < size; ++j) {
22                if (grid[i][j] == 1) {
23                    performDFS(i, j);
24                    foundFirstIsland = true;
25                    break; // Break out of the loops after finding the first island
26                }
27            }
28        }
29      
30        // BFS to find the shortest path to the second island
31        int steps = 0;
32        while (true) {
33            // Iterate over all points added in the last expansion
34            for (int i = queue.size(); i > 0; --i) {
35                int[] point = queue.pollFirst();
36                // Explore all possible directions from current point
37                for (int k = 0; k < 4; ++k) {
38                    int x = point[0] + directions[k];
39                    int y = point[1] + directions[k + 1];
40                  
41                    // Check if the next point is within the grid boundaries
42                    if (x >= 0 && x < size && y >= 0 && y < size) {
43                        // If we reach the second island, return the number of steps
44                        if (grid[x][y] == 1) {
45                            return steps;
46                        }
47                        // If water is found, mark it as visited and add to the queue for further exploration
48                        if (grid[x][y] == 0) {
49                            grid[x][y] = 2;
50                            queue.offer(new int[] {x, y});
51                        }
52                    }
53                }
54            }
55            ++steps; // Increment steps after each level of BFS expansion
56        }
57    }
58
59    // DFS to mark all the squares of the first island
60    private void performDFS(int i, int j) {
61        grid[i][j] = 2; // Mark as visited
62        queue.offer(new int[] {i, j}); // Add to queue for BFS later
63      
64        // Explore all directions from the current square
65        for (int k = 0; k < 4; ++k) {
66            int x = i + directions[k];
67            int y = j + directions[k + 1];
68          
69            // If the next square is part of the island, continue DFS
70            if (x >= 0 && x < size && y >= 0 && y < size && grid[x][y] == 1) {
71                performDFS(x, y);
72            }
73        }
74    }
75}
76

1class Solution {
2public:
3    // Directions for traversing the grid - up, right, down, left
4    const static inline vector<int> directions = {-1, 0, 1, 0, -1};
5
6    // Function to find the shortest bridge between two islands on a grid
7    int shortestBridge(vector<vector<int>>& grid) {
8        int n = grid.size(); // Size of the grid
9        queue<pair<int, int>> pointsQueue; // Queue to store the points to be processed
10
11        // Depth-first search (DFS) to find and mark the first island, and fill the pointsQueue
12        function<void(int, int)> dfs = [&](int row, int col) {
13            grid[row][col] = 2; // Mark as visited with a different value to avoid revisiting
14            pointsQueue.emplace(row, col); // Enqueue the current cell
15            for (int k = 0; k < 4; ++k) { // Traverse the adjacent cells
16                int newRow = row + directions[k];
17                int newCol = col + directions[k + 1];
18                if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < n && grid[newRow][newCol] == 1) {
19                    dfs(newRow, newCol); // Continue DFS if we hit an unvisited cell of the first island
20                }
21            }
22        };
23
24        // Execute DFS to find and mark the first island
25        bool found = false;
26        for (int i = 0; i < n && !found; ++i) {
27            for (int j = 0; j < n; ++j) {
28                if (grid[i][j] == 1) {
29                    dfs(i, j); // Start DFS from the first cell that is part of an island
30                    found = true; // We found the first island
31                    break;
32                }
33            }
34        }
35
36        // Perform a breadth-first search (BFS) to find the shortest path to the second island
37        int distance = 0;
38        while (!pointsQueue.empty()) {
39            // Process all points at the current distance from the first island
40            for (int i = pointsQueue.size(); i > 0; --i) {
41                auto [row, col] = pointsQueue.front();
42                pointsQueue.pop();
43
44                // Explore all four directions from the current cell
45                for (int k = 0; k < 4; ++k) {
46                    int newRow = row + directions[k];
47                    int newCol = col + directions[k + 1];
48                    if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < n) {
49                        if (grid[newRow][newCol] == 1) {
50                            // Return the distance if we reach a cell of the second island
51                            return distance;
52                        }
53                        if (grid[newRow][newCol] == 0) {
54                            // Mark the cell as visited and enqueue if it's part of the water
55                            grid[newRow][newCol] = 2;
56                            pointsQueue.emplace(newRow, newCol);
57                        }
58                    }
59                }
60            }
61            ++distance; // Increase the distance after every level of BFS is processed
62        }
63
64        // This line should never be reached as the function returns upon reaching the second island
65        return -1;
66    }
67};
68

1// Directions for traversing the grid: up, right, down, left
2const directions: number[] = [-1, 0, 1, 0, -1];
3
4// Helper function to perform depth-first search (DFS) to find and mark the first island, and fill the pointsQueue
5function dfs(grid: number[][], row: number, col: number, pointsQueue: [number, number][]) {
6  grid[row][col] = 2; // Mark as visited with a different value to distinguish from unvisited land
7  pointsQueue.push([row, col]); // Enqueue the current cell
8  for (let k = 0; k < 4; ++k) { // Traverse the adjacent cells
9    let newRow = row + directions[k];
10    let newCol = col + directions[k + 1];
11    if (newRow >= 0 && newRow < grid.length && newCol >= 0 && newCol < grid.length && grid[newRow][newCol] === 1) {
12      dfs(grid, newRow, newCol, pointsQueue); // Continue DFS if we hit an unvisited cell of the first island
13    }
14  }
15}
16
17// Function to find the shortest bridge between two islands on a grid
18function shortestBridge(grid: number[][]): number {
19  const n = grid.length; // Size of the grid
20  let pointsQueue: [number, number][] = []; // Queue to store points to be processed
21
22  // Execute DFS to find and mark the first island
23  let found = false;
24  for (let i = 0; i < n && !found; ++i) {
25    for (let j = 0; j < n; ++j) {
26      if (grid[i][j] === 1) {
27        dfs(grid, i, j, pointsQueue); // Start DFS from the first cell that is part of an island
28        found = true; // We found the first island
29        break;
30      }
31    }
32  }
33
34  // Perform a breadth-first search (BFS) to find the shortest path to the second island
35  let distance = 0;
36  while (pointsQueue.length > 0) {
37    // Process all points at the current distance from the first island
38    for (let i = pointsQueue.length; i > 0; --i) {
39      let [row, col] = pointsQueue.shift() || [0, 0];
40
41      // Explore all four directions from the current cell
42      for (let k = 0; k < 4; ++k) {
43        let newRow = row + directions[k];
44        let newCol = col + directions[k + 1];
45        if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < n) {
46          if (grid[newRow][newCol] === 1) {
47            // Return the distance if we reach a cell of the second island
48            return distance;
49          }
50          if (grid[newRow][newCol] === 0) {
51            // Mark the cell as visited and enqueue if it's part of the water
52            grid[newRow][newCol] = 2;
53            pointsQueue.push([newRow, newCol]);
54          }
55        }
56      }
57    }
58    distance++; // Increase the distance after every level of BFS is processed
59  }
60
61  // This line should never be reached as the function returns upon reaching the second island
62  throw new Error('The function did not find the second island, which should not happen with valid input.');
63}
64

Time and Space Complexity

The time complexity of the given code can be considered in two major parts: the Depth First Search (DFS) to find the first island and paint it to a different color (in this case 2), and then performing a Breadth First Search (BFS) to find the shortest path to the second island.

DFS Complexity: The DFS runs at most once for every cell in the grid (n * n where n is the length of a side of the grid). In the worst case, the entire grid is one island and we visit every cell once. Therefore, the time complexity of the DFS is O(n^2).
BFS Complexity: For BFS, in the worst case, we might have to go through all cells in the grid again to find the shortest path to the second island. The BFS visits each cell at most once, so this is also O(n^2).
pairwise Function: The pairwise function on dirs can be seen as O(1) since dirs has a constant size of 5 elements regardless of the input size n. Thus, the loops utilizing pairwise(dirs) do not significantly affect the asymptotic time complexity.

Thus, combining DFS and BFS gives us a total time complexity of O(n^2) as both operations are bound by the size of the grid and do not exceed it.

For space complexity:

The queue q might hold all cells in the worst case (if they all become part of the BFS queue), hence it requires up to O(n^2) space.
The recursive stack for DFS could, in the worst-case scenario (one large island), also take up to O(n^2) space depending on the implementation of the system stack (since we might have to go as deep as the number of cells in the grid if they are all connected in a straight line).

Therefore, the overall space complexity of the algorithm is also O(n^2) due to the usage of the BFS queue and the system stack for recursion in DFS.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What does the following code do?

1def f(arr1, arr2):
2  i, j = 0, 0
3  new_arr = []
4  while i < len(arr1) and j < len(arr2):
5      if arr1[i] < arr2[j]:
6          new_arr.append(arr1[i])
7          i += 1
8      else:
9          new_arr.append(arr2[j])
10          j += 1
11  new_arr.extend(arr1[i:])
12  new_arr.extend(arr2[j:])
13  return new_arr
14

1public static List<Integer> f(int[] arr1, int[] arr2) {
2  int i = 0, j = 0;
3  List<Integer> newArr = new ArrayList<>();
4
5  while (i < arr1.length && j < arr2.length) {
6      if (arr1[i] < arr2[j]) {
7          newArr.add(arr1[i]);
8          i++;
9      } else {
10          newArr.add(arr2[j]);
11          j++;
12      }
13  }
14
15  while (i < arr1.length) {
16      newArr.add(arr1[i]);
17      i++;
18  }
19
20  while (j < arr2.length) {
21      newArr.add(arr2[j]);
22      j++;
23  }
24
25  return newArr;
26}
27

1function f(arr1, arr2) {
2  let i = 0, j = 0;
3  let newArr = [];
4  
5  while (i < arr1.length && j < arr2.length) {
6      if (arr1[i] < arr2[j]) {
7          newArr.push(arr1[i]);
8          i++;
9      } else {
10          newArr.push(arr2[j]);
11          j++;
12      }
13  }
14  
15  while (i < arr1.length) {
16      newArr.push(arr1[i]);
17      i++;
18  }
19  
20  while (j < arr2.length) {
21      newArr.push(arr2[j]);
22      j++;
23  }
24  
25  return newArr;
26}
27

Find the intersection of two arrays.

Check if one array is a subsequence of the other.

Merge two sorted arrays.

Finding median values of 2 arrays.

I don't know