934. Shortest Bridge - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Description:
You are given an n x n binary matrix grid where 0 represents water and 1 represents land. There are exactly two islands in the grid. An island is a group of 1's connected horizontally or vertically. 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
Explanation:
Flip either the top-left 0 or the bottom-right 0 to connect the islands.

Example 2:

Input:

grid = [
  [0,1,0],
  [0,0,0],
  [0,0,1]
]

Output: 2
Explanation:
The optimal solution is to flip the two 0's in the middle row to connect the island at (0,1) with the island at (2,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
Explanation:
Flipping one 0 in the center (for example, at (2,1)) is enough to connect the inner island with the outer island.

Constraints:

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

Hints

Hint 1:
Since there are exactly two islands, you can first identify one island by scanning the grid. Use a depth-first search (DFS) or breadth-first search (BFS) to mark all the cells belonging to one island.
Hint 2:
After marking the first island, use a multi-source BFS starting from all cells in that island. Expand level by level until you reach the second island. The number of levels expanded is the minimum number of flips required.
Hint 3:
Be sure to mark cells as visited during both DFS and BFS to avoid redundant processing.

Approaches

Approach 1: DFS + BFS (Optimal)

Identify the First Island (DFS):
- Scan the grid until you find a cell with value 1.
- Use DFS (or BFS) to traverse and mark all cells of the first island (for example, change them to 2 or add them to a visited set).
- Add these island cells to a queue for the BFS phase.
Expand Using BFS:
- Start a multi-source BFS from all the cells in the first island simultaneously.
- At each level, check the adjacent cells. If an adjacent cell is 0, flip it (conceptually) and add it to the BFS queue.
- If an adjacent cell belongs to the second island (i.e., its value is 1 and it has not been visited as part of the first island), then return the current BFS level (the number of 0’s flipped).

Why This Approach Works:

DFS helps to isolate one island completely.
BFS finds the shortest path (minimum number of flips) to reach the second island by expanding in all directions uniformly.

Code Implementations

Python Code

Python3

. . . .

Java Code

Java

. . . .

Complexity Analysis

Time Complexity:
- The DFS phase visits each cell of one island once: O(n²) in the worst case.
- The BFS phase, in the worst case, can also traverse nearly all cells: O(n²).
- Overall: O(n²), where n is the number of rows/columns in the grid.
Space Complexity:
- The recursion stack for DFS and the BFS queue can store up to O(n²) cells in the worst-case scenario.
- Overall: O(n²).

Step-by-Step Walkthrough

Find the First Island (DFS):
- Iterate through the grid until you find the first cell with a value of 1.
- Use DFS to mark all cells in this island (e.g., change their value to 2) and add them to the BFS queue.
Perform BFS to Expand Outward:
- Start BFS from all the cells of the first island simultaneously.
- For each cell in the queue, check its four neighbors.
- If a neighbor is water (0), mark it as visited (change it to 2) and add it to the queue.
- If a neighbor is part of the second island (value 1), return the current BFS level, which represents the minimum number of flips needed.
Terminate and Return:
- The BFS will expand level by level until it encounters a cell from the second island. The level (or steps count) at that point is the answer.

Visual Example

Consider the grid:

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

Step 1:
Find the first island (e.g., starting at (0,1)) and mark it (all connected 1's become 2).
After DFS, the grid may look like:
```
[
  [0, 2, 0, 0],
  [0, 2, 0, 0],
  [0, 0, 0, 1],
  [0, 0, 0, 1]
]
```
The queue now contains: [(0,1), (1,1)].
Step 2:
Start BFS from these cells. In the first level, expand to adjacent water cells.
For example, from (0,1) explore (0,0), (0,2), (1,1) (already 2), and (-1,1) (out of bounds).
Continue expanding until you reach one of the cells belonging to the second island (cells with 1 at (2,3) or (3,3)).
Step 3:
The number of BFS levels required to reach the second island equals the minimum flips needed.

Common Mistakes

Not Marking Visited Cells:
Failing to mark cells properly in DFS or BFS can lead to infinite loops or redundant processing.
Incorrect BFS Level Counting:
Ensure that the BFS expansion correctly increments the level count after processing all nodes at the current level.
Boundary Handling:
Always check grid boundaries when accessing neighbor cells.

Edge Cases

Islands Already Adjacent:
When the islands are already next to each other, the minimum flips required will be 0 or 1.
Minimal Grid:
When the grid size is at the lower constraint (e.g., 2x2), ensure the algorithm still correctly identifies and connects the islands.

Number of Islands:
A classic problem that involves DFS/BFS to count connected components.
Walls and Gates:
A problem that uses multi-source BFS to update distances.
Flood Fill:
A related problem that uses DFS/BFS to change connected regions.

Number of Islands
Walls and Gates
Flood Fill
Graph Connected Components