Shortest Bridge - Google Top Interview Questions
Problem Statement :
Given a two-dimensional list of integers matrix containing 0s and 1s, 0 represents water and 1 represents land.
An island is a group of connecting 1s in 4 directions that are either surrounded by 0s or by the edges.
Find the shortest bridge that connects two islands.
It is guaranteed that there are two and only two islands.
Constraints
n, m ≤ 250 where n and m are the number of rows and columns in matrix
Example 1
Input
matrix = [
[0, 1],
[1, 0]
]
Output
1
Explanation
Either of the two water elements can be used as the bridge.
Example 2
Input
matrix = [
[1, 0, 0],
[0, 0, 0],
[0, 0, 1]
]
Output
3
Explanation
There's six shortest bridges such as [(0, 1), (0, 2), (1, 2)] or [(1, 0), (2, 0), (2, 1)]
Solution :
Solution in C++ :
void dfs(vector<vector<int>> &matrix, int x, int y, queue<pair<int, int>> &q) {
// Invalid position or cell-state
if (x < 0 || y < 0 || x >= matrix.size() || y >= matrix[0].size() || matrix[x][y] == 2 ||
matrix[x][y] < 0) {
return;
}
// If the cell is a water cell adjacent to the island
// mark it and place it into the bfs queue and return
if (matrix[x][y] == 0) {
matrix[x][y] = -1;
q.emplace(make_pair(x, y));
return;
}
// Mark island cell with different color
if (matrix[x][y] == 1) {
matrix[x][y] = 2;
}
// run dfs to mark neighbors
vector<vector<int>> dirs{{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
for (auto &dir : dirs) {
int x1 = x + dir[0];
int y1 = y + dir[1];
dfs(matrix, x1, y1, q);
}
}
int solve(vector<vector<int>> &matrix) {
int m = matrix.size(), n = m == 0 ? 0 : matrix[0].size();
// Find the first land cell (can be any of the two islands)
// and run dfs to mark the island with a different color
bool landFound = false;
queue<pair<int, int>> q;
for (int x = 0; x < m && !landFound; ++x) {
for (int y = 0; y < n && !landFound; ++y) {
if (matrix[x][y] == 1) {
landFound = true;
dfs(matrix, x, y, q);
}
}
}
// Means that there's no island at all
// so return error
if (q.empty()) {
return -1;
}
// Run bfs from the edges of the marked island
vector<vector<int>> dirs{{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
while (!q.empty()) {
pair<int, int> curr = q.front();
q.pop();
for (auto &dir : dirs) {
int x = curr.first + dir[0];
int y = curr.second + dir[1];
if (x >= 0 && y >= 0 && x < m && y < n) {
// If we have found the second island
// return the distance
// distance is -ve of the current cell
// since we've marked water cells with
// increasing negative values
if (matrix[x][y] == 1) {
return 0 - matrix[curr.first][curr.second];
}
// If it is a water cell, update its distance
// and then add it to the queue
else if (matrix[x][y] == 0) {
matrix[x][y] = matrix[curr.first][curr.second] - 1;
q.emplace(make_pair(x, y));
}
}
}
}
// We didn't find the second island so return error
return -1;
}
Solution in Java :
import java.util.*;
class Solution {
private static final int[] DIRS = {-1, 0, 1, 0, -1};
private static final int NEWCOLOR = 2;
public int solve(int[][] grid) {
final int R = grid.length, C = grid[0].length;
Queue<int[]> q = new ArrayDeque<>();
findIsland(grid, R, C, q);
for (int step = 0; q.isEmpty() == false; step++) {
for (int b = q.size(); b != 0; b--) {
int[] now = q.poll();
for (int i = 0; i != 4; i++) {
final int nr = now[0] + DIRS[i], nc = now[1] + DIRS[i + 1];
if (nr == -1 || nr == R || nc == -1 || nc == C || grid[nr][nc] == NEWCOLOR)
continue;
if (grid[nr][nc] == 1)
return step;
grid[nr][nc] = NEWCOLOR;
q.offer(new int[] {nr, nc});
}
}
}
return -1;
}
private void findIsland(int[][] grid, final int R, final int C, Queue<int[]> q) {
for (int r = 0; r != R; r++)
for (int c = 0; c != C; c++)
if (grid[r][c] == 1) {
drown(grid, R, C, r, c, NEWCOLOR, q);
return;
}
}
private void drown(int[][] grid, int R, int C, int r, int c, int color, Queue<int[]> q) {
if (r == R || c == C || r == -1 || c == -1 || grid[r][c] != 1)
return;
grid[r][c] = color;
q.offer(new int[] {r, c});
for (int i = 0; i != 4; i++) drown(grid, R, C, r + DIRS[i], c + DIRS[i + 1], color, q);
}
}
Solution in Python :
class Solution:
def solve(self, matrix):
cnt = 0
rows = len(matrix)
columns = len(matrix[0])
visited = {}
for i in range(2):
flag = True
while flag:
column = cnt % columns
row = cnt // columns
if (row, column) not in visited:
visited[(row, column)] = 0
if matrix[row][column] == 1:
flag = False
matches = {(row, column): 0}
self.find_touching(matrix, visited, matches, row, column, rows, columns)
cnt += 1
if i == 0:
island_one = self.find_outline(matches)
print(island_one)
else:
island_two = self.find_outline(matches)
print(island_two)
best = -1
for pos1 in island_one:
for pos2 in island_two:
needed = abs(pos1[0] - pos2[0]) + abs(pos1[1] - pos2[1]) - 1
if best == -1 or needed < best:
best = needed
return best
def find_touching(self, matrix, visited, matches, row, column, rows, columns):
moves = [(-1, 0), (0, -1), (0, 1), (1, 0)]
for move in moves:
new_row = row + move[0]
new_column = column + move[1]
if (new_row, new_column) not in visited:
if new_row >= 0 and new_row < rows:
if new_column >= 0 and new_column < columns:
visited[(new_row, new_column)] = 0
if matrix[new_row][new_column] == 1:
matches[(new_row, new_column)] = 0
self.find_touching(
matrix, visited, matches, new_row, new_column, rows, columns
)
return matrix
def find_outline(self, matches):
keys = list(matches.keys())
for item in keys:
flag = True
for direction in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
if (item[0] + direction[0], item[1] + direction[1]) not in matches:
flag = False
break
if flag:
matches[item] = -1
return [x for x in matches if matches[x] == 0]
View More Similar Problems
Direct Connections
Enter-View ( EV ) is a linear, street-like country. By linear, we mean all the cities of the country are placed on a single straight line - the x -axis. Thus every city's position can be defined by a single coordinate, xi, the distance from the left borderline of the country. You can treat all cities as single points. Unfortunately, the dictator of telecommunication of EV (Mr. S. Treat Jr.) do
View Solution →Subsequence Weighting
A subsequence of a sequence is a sequence which is obtained by deleting zero or more elements from the sequence. You are given a sequence A in which every element is a pair of integers i.e A = [(a1, w1), (a2, w2),..., (aN, wN)]. For a subseqence B = [(b1, v1), (b2, v2), ...., (bM, vM)] of the given sequence : We call it increasing if for every i (1 <= i < M ) , bi < bi+1. Weight(B) =
View Solution →Kindergarten Adventures
Meera teaches a class of n students, and every day in her classroom is an adventure. Today is drawing day! The students are sitting around a round table, and they are numbered from 1 to n in the clockwise direction. This means that the students are numbered 1, 2, 3, . . . , n-1, n, and students 1 and n are sitting next to each other. After letting the students draw for a certain period of ti
View Solution →Mr. X and His Shots
A cricket match is going to be held. The field is represented by a 1D plane. A cricketer, Mr. X has N favorite shots. Each shot has a particular range. The range of the ith shot is from Ai to Bi. That means his favorite shot can be anywhere in this range. Each player on the opposite team can field only in a particular range. Player i can field from Ci to Di. You are given the N favorite shots of M
View Solution →Jim and the Skyscrapers
Jim has invented a new flying object called HZ42. HZ42 is like a broom and can only fly horizontally, independent of the environment. One day, Jim started his flight from Dubai's highest skyscraper, traveled some distance and landed on another skyscraper of same height! So much fun! But unfortunately, new skyscrapers have been built recently. Let us describe the problem in one dimensional space
View Solution →Palindromic Subsets
Consider a lowercase English alphabetic letter character denoted by c. A shift operation on some c turns it into the next letter in the alphabet. For example, and ,shift(a) = b , shift(e) = f, shift(z) = a . Given a zero-indexed string, s, of n lowercase letters, perform q queries on s where each query takes one of the following two forms: 1 i j t: All letters in the inclusive range from i t
View Solution →