934. Shortest Bridge
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.
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 a2. 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 a2and 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 a1during this expansion, it means we have reached the second island, and the current distance (or the number of0s converted to2s) 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.
Which two pointer techniques do you use to check if a string is a palindrome?
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
dirsto represent the four cardinal directions for traversal. We then find a starting point, which is the first1encountered 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 with2to distinguish it from the other unvisited land cells (1) and water (0). For every cell marked as2, we continue the DFS for each of its unvisited land neighbors by recursively calling the DFS function. We also add the cells to a queueq, 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 variableansto keep track of the number of flips required. During the BFS, we dequeue cells fromqand 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 theansvariable 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.
- If the cell is water
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.
What data structure does Breadth-first search typically uses to store intermediate states?
Example Walkthrough
Let's consider a small 5x5 binary matrix grid as an example to walk through the solution approach.
1Grid: 20 1 0 0 0 30 1 0 0 0 40 0 0 1 1 50 0 0 0 0 60 0 0 0 1
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:
10 2 0 0 0 20 2 0 0 0 30 0 0 1 1 40 0 0 0 0 50 0 0 0 1
- Now, all the cells from the first island are marked as
2, and we create a queueqwith 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,
ansis 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):
10 2 2 0 0 20 2 2 0 0 30 0 0 1 1 40 0 0 0 0 50 0 0 0 1 6ans = 1 (since we transformed one '0' to '2')
Second iteration of BFS (continuing to expand):
10 2 2 2 0 20 2 2 2 0 30 0 0 1 1 40 0 0 0 0 50 0 0 0 1 6ans = 2
Third iteration of BFS (the frontier now touches the second island):
10 2 2 2 0 20 2 2 2 0 30 0 0 1 1 40 0 0 0 0 50 0 0 0 1 6ans = 2
- The BFS stops here as the expanding cells meet the second island, which is still marked with
1s. The minimum number of flips is2, 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
411class 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}
761class 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};
681// 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}
64What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?
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 * nwherenis 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 isO(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
pairwisefunction ondirscan be seen asO(1)sincedirshas a constant size of 5 elements regardless of the input sizen. Thus, the loops utilizingpairwise(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
qmight hold all cells in the worst case (if they all become part of the BFS queue), hence it requires up toO(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.
A heap is a ...?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.