In a given 2D binary array grid, there are two islands. (An island is a 4-directionally connected group of 1s not connected to any other 1s.)
Now, we may change 0s to 1s so as to connect the two islands together to form 1 island.
Return the smallest number of 0s that must be flipped. (It is guaranteed that the answer is at least 1.)
Example 1:
Input: grid = [[0,1],[1,0]] Output: 1
Example 2:
Input: grid = [[0,1,0],[0,0,0],[0,0,1]] Output: 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
Constraints:
2 <= grid.length == grid[0].length <= 100grid[i][j] == 0 or grid[i][j] == 1
The description was taken from https://leetcode.com/problems/shortest-bridge/.
#O(N^2) Time, O(N^2) Space
class Solution:
def shortestBridge(self, grid: List[List[int]]) -> int:
n = len(grid)
queue = collections.deque() def in_bounds(row:int, col:int) -> bool:
if row < 0 or col < 0 or row >= n or col >= n:
return False
return True
def dfs(row:int, col:int) -> None:
if not in_bounds(row, col) or grid[row][col] != 1:
return
grid[row][col] = 2
queue.append((row, col))
dfs(row, col-1)
dfs(row, col+1)
dfs(row-1, col)
dfs(row+1,col)
def bfs() -> int:
seen = set()
distance = 0
neighbors = [(0,1),(1,0),(0,-1),(-1,0)]
while queue:
width = len(queue)
for _ in range(width):
row,col = queue.popleft()
if grid[row][col] == 1:
return distance -1
for neighbor in neighbors:
next_row, next_col = row+neighbor[0], col+neighbor[1]
if in_bounds(next_row, next_col) and (next_row, next_col) not in seen:
queue.append((next_row, next_col))
seen.add((next_row, next_col))
distance += 1 for row in range(n):
for col in range(n):
if grid[row][col] == 1:
dfs(row, col)
return bfs()
Typically if we're trying to find the shortest path within a graph or matrix, a Breadth-First Search approach is favorable to a Depth-First Search since a DFS would be taking detours in the path instead of taking a linear, layer-by-layer path.
However, If we were to just try and perform a BFS on one of the islands to get the shortest path to the other, how would we distinguish which island is which since they're both comprised of ones?
What we can do is perform a DFS on the first island we see and change the identifier to be distinguishable from the other island, then we can perform a BFS on that island and see how long it takes us to hit the other.
Let's start by caching the length of the grid so that we don't have to keep calculating it within our functions, and also by initializing an empty queue. We want this queue to be accessible from both the DFS and BFS functions so we will create it here in this outer function.
n = len(grid)
queue = collections.deque()
Next, we will create a helper function that will let us know if the current cell we are trying to access is inbounds of the matrix so that we don't have to keep rewriting this statement.
def in_bounds(row:int, col:int) -> bool:
if row < 0 or col < 0 or row >= n or col >= n:
return False
return True
Now let's make our Depth-First Search function.
The function will take a row and column cell coordinate as arguments.
def dfs(row:int, col:int) -> None:
First off, our base case will be if we hit a cell out of bounds or a cell that isn't a one, we will want to return. If the cell isn't a one, then it is either a two in which we are revising the same piece of land or a zero in which case we are no longer on the island.
if not in_bounds(row, col) or grid[row][col] != 1:
return
What we will want to do is change the identifier of this island from one to two, this could really be any value but this will let us distinguish this island from the other and will also keep us from revisiting the same island.
grid[row][col] = 2
We will also want to add each piece of this island to the queue because the entire island is where we will be starting the BFS from.
queue.append((row, col))
Once we have processed each cell, we will want to do the same thing but for the left, right, top, and bottom neighbors.
dfs(row, col-1)
dfs(row, col+1)
dfs(row-1, col)
dfs(row+1,col)
We've got our DFS function built, now let's build our BFS function which will return the shortest path to the next island.
def bfs() -> int:
Let's start by initializing our seen cell hashset to stop us from revisiting cells, our initial path distance of zero, and a list of delta coordinates which will let us easily find the four neighbors of each cell.
seen = set()
distance = 0
neighbors = [(0,1),(1,0),(0,-1),(-1,0)]
While we still have cells in our queue, which will initially have the entire first island in it, we will continue searching for a bridge to the next island.
while queue:
Within our BFS, we will start by calculating the width of the queue because that will let us know how many cells are in the current layer.
width = len(queue)
Then, within that layer, we will pop each cell from the queue and check if it is a piece of the next island.
We will want to subtract one from the distance because it will be including the distance to get to the land of the island but we only need the distance that needs to be crossed on water for the bridge.
for _ in range(width):
row,col = queue.popleft()
if grid[row][col] == 1:
return distance -1
If not, we will calculate its four neighbors and if they are in the bounds of the matrix and unseen, we will add them to the queue.
for neighbor in neighbors:
next_row, next_col = row+neighbor[0], col+neighbor[1]
if in_bounds(next_row, next_col) and (next_row, next_col) not in seen:
queue.append((next_row, next_col))
seen.add((next_row, next_col))
Once we have finished searching through an entire layer, we will increment the path distance by one and continue to the next layer.
distance += 1
Now that we have all of our functions built, we will begin our traversal through the matrix.
for row in range(n):
for col in range(n):
If we encounter the first island, we will run a DFS to change the identifier of each piece of land in the island and add each piece of land to the queue.
if grid[row][col] == 1:
dfs(row, col)
| 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 |
| 2 | 0 | 1 | 0 | 2 |
| 2 | 0 | 0 | 0 | 2 |
| 2 | 2 | 2 | 2 | 2 |
Once we have finished with that first island, we can immediately run the BFS to find the path from that island just searched to the other island.
| 2 | 2 | 2 | 2 | 2 |
| 2 | 0 | 0 | 0 | 2 |
| 2 | 0 | 1 | 0 | 2 |
| 2 | 0 | 0 | 0 | 2 |
| 2 | 2 | 2 | 2 | 2 |
return bfs()