Problem Statement:-
You are given an n x n binary matrix grid where 1 represents land and 0 represents water.
An island is a 4-directionally connected group of 1's not connected to any other 1's. There are exactly two islands in grid.
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.
Link: https://leetcode.com/problems/shortest-bridge/description/
Problem Explanation with examples:-
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
n == grid.length == grid[i].length2 <= n <= 100grid[i][j]is either0or1.There are exactly two islands in
grid.
Intuition:-
It is given that there will be only 2 islands.
So, if we find the first island, we can use bfs to go layer by layer and find the shortest distance to the second island.
We can use dfs to find the first island and then use bfs to find the shortest distance to the second island.
Solution:-
Take the length of the grid and define the directions list.
Define a function invalid that takes in a row and column and returns if the row or column is out of bounds of the grid.
Define a visit set.
Define a dfs function that takes in a row and column as parameters.
If the row or column is invalid or the value at the row and column is 0 or the row and column is in the visit set, then return.
Else, add the row and column to the visit set and iterate through each direction in the directions list. Call the dfs function on the row + the row of the direction and the column + the column of the direction.
Then, define a bfs function.
Define a res variable and a queue that is initialized to the visit set.
While the queue is not empty, iterate through each element in the queue.
Pop the row and column from the queue and iterate through each direction in the directions list.
Define a curr and curc variable that is the row + the row of the direction and the column + the column of the direction.
If the curr or curc is invalid or the curr and curc is in the visit set, then continue.
If the value at the curr and curc is 1, then return the res variable.
Else, append the curr and curc to the queue and add the curr and curc to the visit set.
Increment the res variable by 1.
After the bfs function, iterate through each row and column in the grid and if the value at the row and column is 1, then call the dfs function on the row and column. This will find the first island. Then, return the bfs function. This will find the shortest distance to the second island.
Code:-
JAVA Solution
class Solution {
private int[][] grid;
private int n;
private int[][] dirc = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
private Set<String> visit;
private boolean invalid(int r, int c) {
return r < 0 || c < 0 || r >= n || c >= n;
}
private void dfs(int r, int c) {
if (invalid(r, c) || grid[r][c] == 0 || visit.contains(r + "," + c)) {
return;
}
visit.add(r + "," + c);
for (int[] dir : dirc) {
dfs(r + dir[0], c + dir[1]);
}
}
public int shortestBridge(int[][] grid) {
this.grid = grid;
this.n = grid.length;
this.visit = new HashSet<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
dfs(i, j);
return bfs();
}
}
}
return -1; // Indicates no bridge found
}
private int bfs() {
int res = 0;
Queue<int[]> queue = new LinkedList<>();
for (String cell : visit) {
String[] parts = cell.split(",");
int r = Integer.parseInt(parts[0]);
int c = Integer.parseInt(parts[1]);
queue.add(new int[]{r, c});
}
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] cell = queue.poll();
int r = cell[0];
int c = cell[1];
for (int[] dir : dirc) {
int curr = r + dir[0];
int curc = c + dir[1];
if (invalid(curr, curc) || visit.contains(curr + "," + curc)) {
continue;
}
if (grid[curr][curc] == 1) {
return res;
}
queue.add(new int[]{curr, curc});
visit.add(curr + "," + curc);
}
}
res++;
}
return -1; // Indicates no bridge found
}
}
Python Solution
class Solution:
def shortestBridge(self, grid: List[List[int]]) -> int:
n = len(grid)
dirc = [[0,1],[1,0],[0,-1],[-1,0]]
def invalid(r,c):
return r < 0 or c < 0 or r >= n or c >= n
visit = set()
def dfs(r,c):
if invalid(r,c) or not grid[r][c] or (r,c) in visit:
return
visit.add((r,c))
for dr,dc in dirc:
dfs(r+dr, c+dc)
def bfs():
res = 0
q = deque(visit)
while q:
for i in range(len(q)):
r,c = q.popleft()
for dr, dc in dirc:
curr, curc = r+dr, c+dc
if invalid(curr,curc) or (curr,curc) in visit:
continue
if grid[curr][curc]:
return res
q.append([curr,curc])
visit.add((curr,curc))
res += 1
for i in range(n):
for j in range(n):
if grid[i][j]:
dfs(i,j)
return bfs()
Complexity Analysis:-
TIME:-
The time complexity is is O(N^2) because we have to iterate over the grid to find the initial island and perform both DFS and BFS on the grid. Here, N represents the length of one side of the grid.
SPACE:-
The space complexity is O(N^2) because we use sets to keep track of visited cells and the queue in BFS can potentially hold all the cells in the grid in the worst case.