Solution: Shortest Bridge

Grokking Graph Algorithms for Coding Interviews

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Shortest Bridge

Table of Contents

Contents are not accessible

Problem Statement

You are given a square grid (n x n) made up of 1s (land) and 0s (water). There are exactly two separate islands in the grid.

An island is defined as a group of connected 1s that are not connected to any other 1s.

Return the minimum number of 0s that need to be flipped to connect the two islands into one if you can change any 0 to 1 to connect the two islands.

Examples

Example 1:

Input: grid =

[[1, 1, 0, 0, 0],
 [1, 0, 0, 0, 0],
 [0, 0, 1, 1, 0],
 [0, 0, 0, 1, 1],
 [0, 0, 0, 0, 0]]

Expected Output: 2
Explanation: Changing the zeros at (1,1) and (1,2) will connect the two islands. Also, changing the zeros at (1,1) and (2,1) will connect the two islands.

Example 2:

Input: grid =

[[0, 0, 0, 1, 1],
 [0, 0, 0, 1, 0],
 [0, 0, 0, 0, 0],
 [0, 0, 0, 0, 1],
 [0, 0, 0, 0, 1]]

Expected Output: 2
Explanation: Changing the zeros at (1,4) and (2,4) or (2, 3) and (2, 4) will connect the two islands.

Example 3:

Input: grid =

[[0, 1, 0],
 [0, 1, 0],
 [0, 0, 1]]

Expected Output: 1
Explanation: Changing the zero at (1,2) will connect the two islands.

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.

Solution

To solve this problem, the key idea is to identify and expand the first islands in a systematic manner. Initially, we use Depth-First Search (DFS) to locate and mark all the cells of the first island. This step involves traversing through the grid until we find the first island cell, and then recursively marking all connected land cells with 2. We also add these cells to a queue, which will be used for the Breadth-First Search (BFS) in the next step.

Once the first island is marked and its cells are in the queue, we use BFS to expand from the boundary of this island. In BFS, we process each cell in the queue, exploring its neighboring cells. If we encounter an unmarked water cell, we mark it and add it to the queue. If we encounter a cell from the second island, we return the current distance, as this indicates we have found the shortest bridge connecting the two islands. This approach ensures that we explore all possible paths in an expanding wavefront manner, guaranteeing that the first encounter with the second island is the shortest path.

Step-by-Step Algorithm

Identify and Mark the First Island:
- Traverse the grid to find the first occurrence of a '1'.
- Use Depth-First Search (DFS) to mark all connected '1's of the first island with a different value (say '2') to distinguish it from the other island.
- Add all these marked '2' cells to a queue for further processing.
Breadth-First Search (BFS) to Expand the First Island:
- Use the queue from the previous step to perform BFS.
- For each cell in the queue, check its four neighbors (Right, down, left, up).
- If a neighbor is part of the second island (value '1'), return the number of steps taken, as it represents the minimum number of flips needed to connect the islands.
- If a neighbor is water (value '0'), change it to '2', add it to the queue, and continue the BFS.
Keep Track of Steps:
- Use a variable to count the number of BFS levels processed. Each level corresponds to one step in the BFS, which translates to one flip of a '0' to a '1'.

Algorithm Walkthrough

Given grid:

[[1, 1, 0, 0, 0],
 [1, 0, 0, 0, 0],
 [0, 0, 1, 1, 0],
 [0, 0, 0, 1, 1],
 [0, 0, 0, 0, 0]]

Initialization:
- queue = []
- steps = 0
DFS to Mark the First Island:
- Start from the first '1' at (0, 0).
- Mark (0, 0) as '2' and add to queue: queue = [(0, 0)].
- Mark (0, 1) as '2' and add to queue: queue = [(0, 0), (0, 1)].
- Mark (1, 0) as '2' and add to queue: queue = [(0, 0), (0, 1), (1, 0)].
Updated grid:
```
[[2, 2, 0, 0, 0],
 [2, 0, 0, 0, 0],
 [0, 0, 1, 1, 0],
 [0, 0, 0, 1, 1],
 [0, 0, 0, 0, 0]]
```
BFS to Find the Shortest Bridge:
- Step 1:
  - steps = 0
  - Process cells: [(0, 0), (0, 1), (1, 0)]
  - Expand from (0, 0):
    - (0, 1) is already '2'.
    - (1, 0) is already '2'.
    - (0, -1) and (-1, 0) are out of bounds.
  - Expand from (0, 1):
    - (0, 2) is '0', change to '2' and add to queue: queue = [(1, 0), (0, 2)].
    - (1, 1) is '0', change to '2' and add to queue: queue = [(1, 0), (0, 2), (1, 1)].
    - (0, 0) is already '2'.
    - (-1, 1) is out of bounds.
  - Expand from (1, 0):
    - (1, 1) is already '2'.
    - (2, 0) is '0', change to '2' and add to queue: queue = [(0, 2), (1, 1), (2, 0)].
    - (1, -1) and (0, 0) are already '2'.
  Updated grid:
```
[[2, 2, 2, 0, 0],
 [2, 2, 0, 0, 0],
 [2, 0, 1, 1, 0],
 [0, 0, 0, 1, 1],
 [0, 0, 0, 0, 0]]
```
- Step 2:
  - steps = 1
  - Process cells: [(0, 2), (1, 1), (2, 0)]
  - Expand from (0, 2):
    - (0, 3) is '0', change to '2' and add to queue: queue = [(1, 1), (2, 0), (0, 3)].
    - (1, 2) is '0', change to '2' and add to queue: queue = [(1, 1), (2, 0), (0, 3), (1, 2)].
    - (0, 1) is already '2'.
    - (-1, 2) is out of bounds.
  - Expand from (1, 1):
    - (1, 2) is already '2'.
    - (2, 1) is '0', change to '2' and add to queue: queue = [(2, 0), (0, 3), (1, 2), (2, 1)].
    - (1, 0) is already '2'.
    - (0, 1) is already '2'.
  - Expand from (2, 0):
    - (2, 1) is already '2'.
    - (3, 0) is '0', change to '2' and add to queue: queue = [(0, 3), (1, 2), (2, 1), (3, 0)].
    - (2, -1) and (1, 0) are already '2'.
  Updated grid:
```
[[2, 2, 2, 2, 0],
 [2, 2, 2, 0, 0],
 [2, 2, 1, 1, 0],
 [2, 0, 0, 1, 1],
 [0, 0, 0, 0, 0]]
```
- Step 3:
  - steps = 2
  - Process cells: [(0, 3), (1, 2), (2, 1), (3, 0)]
  - Expand from (0, 3):
    - (0, 4) is '0', change to '2' and add to queue: queue = [(1, 2), (2, 1), (3, 0), (0, 4)].
    - (1, 3) is '0', change to '2' and add to queue: queue = [(1, 2), (2, 1), (3, 0), (0, 4), (1, 3)].
    - (0, 2) is already '2'.
    - (-1, 3) is out of bounds.
  - Expand from (1, 2):
    - (1, 3) is already '2'.
    - (2, 2) is '1', which is part of the second island. Return steps which is 2.
  Final grid:
```
[[2, 2, 2, 2, 2],
 [2, 2, 2, 2, 0],
 [2, 2, 1, 1, 0],
 [2, 0, 0, 1, 1],
 [0, 0, 0, 0, 0]]
```

Thus, the minimum number of flips needed to connect the two islands is 2.

Code

Python3

. . . .

Complexity Analysis:

Time Complexity: The algorithm runs in $O(n^2)$ time. This is because in the worst case, we have to check each cell of the grid twice - once during the DFS to find the first island and once during the BFS to find the shortest bridge.
Space Complexity: The space complexity is $O(n^2)$ due to the space used by the queue for BFS and the recursive stack space for DFS in the worst case.

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible