Imagine you are on an island, enjoying or probably learning :), and see another island right before you. You want to visit it, but hereâ€™s a catch, you canâ€™t take a boat to reach the island. You can swim, but you can see sharks in the ocean, ready to feed on you. You have a gun that can kill the shark but has only one bullet. Now you must find a way to reach the other island by killing at most one shark.

Here consider the sharks to be -1, and the other numbers as islands. Now you have to determine if you can reach the other island, as shown in the grid above.

Problem Statement

More formally, you are given a grid of the size N*M, where N is the number of rows, while M is the number of columns. You are given integers ranging from [1, K] in that grid. The grid also contains 0, meaning unblocked cells, and -1, meaning blocked cells.

Determine if connecting all those K cells is possible by removing/unblocking at most one blocked cell.

Note: All values in the range [1, K] should be present in the grid, in order to connect those K cells.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Sample Examples

Here are some sample example test cases, which we will examine further in our blog.

Example 1

Given a 2-D grid `grid` and an integer K, determine if connecting all K points is possible by removing at most one blocked cell.

Where 0 represents unblocked cells, and the numbered cells are also unblocked. The cells described via -1 are blocked cells and obstacles in connecting all six numbers.

As we see, there are two islands, one formed by 0, 1, 2, 0, and the other one is 5, 6, 3, 4

These two are separated by blocked cells, namely -1. So to connect them, we can either remove the blocked cell at (2,2) or (2,3) [consider 1-based indexing].

On successfully removing one of the obstacles, we can connect all the K cells, so output becomes True.

Example 2

Given a 2-D grid `grid` and an integer K, determine if connecting all K points is possible by removing at most one blocked cell.

Where -1 represents blocked cells, and the numbered cells are unblocked. The cells described via -1 are obstacles in connecting all two numbers.

As we see, there are two islands, one formed by 1 and the other one is 2, and they canâ€™t be joined together via the removal of at most one blocked cell, so we return False.

BFS Approach

Here, we will use a Breadth First Search (BFS) traversal to iterate over the cells. We will transform this problem into counting the number of islands in a grid. We will be counting the different numbers of islands in the grid.

Algorithm

Let's discuss the above approach to get a clear picture.

Step 1: Iterate over the matrix, and append the values which are neither 0 nor -1 to the queue.

Step 2: Append the top element's unblocked neighbor cells/remaining digits to the queue.

Step 3: Again, iterate over the neighbors of the top element, and append the unblocked and remaining digits to the queue.

Step 4: Maintain a visited array, or a set, to ensure no element gets repeated twice in the queue.

Step 5: When all the neighbors have been visited, replace them with any integer, say i, denoting the ith island.

Step 6: Now traverse forward in the matrix, to check if any digit in the range [1, K], is not visited. If not, then append it to the queue, and perform the same steps as above.

Step 7: On reaching the end of the matrix, count the number of islands formed.

Step 8: Now check whether the number of islands in the grid is less than or equal to 2.

If the number of islands exceeds 2, return False, as it will require at least two blocked cells to be removed.

Step 9: Else if the number of islands is two or less than 2, iterate over the blocked cells and check if two different islands surround any blocked cell. If it is the case, return True, else False.

Dry Run

Let's go through the above algorithm with the help of an example.

Example

Given a grid containing the integers from [1, K], determine if by removing at most one blocked cell, we can connect all the integers

Step 1:Maintain a queue called q = [ ], in which we will be appending the values. Declare an empty set called value_set.

Step 2: Now iterate through the grid, and add the element in the queue, only when the node's value is not equal to 0 or -1.

Step 3: First, we encounter the element at index [1,1] (we are following 1-based indexing); since it is 0(unblocked cell), we ignore it and move forward to the next element.

Step 4: Now we arrive at [1,1], as it is neither 0 nor -1, so we append it in the queue, and now we will be checking its neighbors. Here the element is 1, so our queue becomes q=[1]. Add element (1,1) to the visited set.

Step 5: Get all its neighbors, i.e., 2,-1, and 0.

Step 6: Now after appending 2 and 0 to the queue, repeat the same process as above. Append the unblocked / digit neighbors of the top element; also, keep a check to make sure the element doesn't get repeated more than once. So check if the neighbors are present in the visited set; if they do, ignore the element, and move forward. Else append the neighbor to the queue.

Step 7: Now the queue becomes q = [1,2,0]. Since all the neighbors of element 1 have been added to the queue, we pop 1 from the queue and then repeat the same process.

Step 8: Maintain a variable curr = 1, representing the number of islands found.

Step 9: The top element becomes 2, and its neighbors are added to the queue.

Step 10: We create a copy of the above matrix, ans_grid, and will be updating the value of the visited coordinates in ans_grid to be the value of curr i.e., a current number of islands.

Step 11: Now 0 is on top, and no neighbors can be appended to the queue, so we pop it as well.

Step 12: Now the queue is empty, and so we will be moving forward in the matrix.

Step 13: Elements 5,6,3 and 4 are left, and now adding them to the queue, and performing similar operations to get another island, containing those numbers.

Step 14: Now when we reach the end of the matrix, we want to check if all the elements in the range [1, K] are present. So we iterate over the visited set, and add the corresponding value present in the grid at that index, to another set value_set.

Step 15: Iterate over the range [1, K] and check if every value is present in the value_set. If any value is not present, return False.

Step 16: If all the values are present in value_set. Then check for removal of at most one blocked cell. Iterate over all the blocked cells in ans_grid, and check if any cell, has two different types of islands as neighbors. If they do, return True, else False.

Implementation in Python

from collections import deque
from copy import deepcopy
def generate_islands(grid: list, number_of_islands: int) -> tuple:
visited = set()
# New 2-d grid, of same values
ans_grid = deepcopy(grid)
# Helper array, for traversing through neighbors
neighbors = [[1, 0], [0, 1], [-1, 0], [0, -1]]
m, n = len(grid), len(grid[0])
# Traversing through the grid
for i in range(m):
for j in range(n):
curr_ele = grid[i][j]
# Starting the bfs at a digit between 1,K
if curr_ele != 0 and curr_ele != -1 and (i, j) not in visited:
number_of_islands += 1
visited.add((i, j))
# Adding cordinates to the queue
q = deque([(i, j)])
while q:
# Breadth first search begins
top = q.popleft()
top_x, top_y = top[0], top[1]
# Changing the value of the newly formed grid
ans_grid[top_x][top_y] = number_of_islands
# Traversing through the neighbors of x,y
for x, y in neighbors:
X, Y = x + top_x, y + top_y
# Basic condition check
if (
0 <= X < m
and 0 <= Y < n
and grid[X][Y] != -1
and (X, Y) not in visited
):
visited.add((X, Y))
q.append((X, Y))
# Returns a tuple of island grid, and total number of islands
return (ans_grid, number_of_islands, visited)
# This function checks, if on removing at most one
# blocked cell, can the points be connected or not
def can_be_connected(island_grid: int, number_of_islands: list, value_set: set, K: int) -> bool:
# Initial check of all elements in range [1,K]
# to be present and visited inside grid
for i in range(1,K+1):
if i not in value_set:
return False
# Base condition, if number of islands is 1
# then return True
if number_of_islands == 1:
return True
# Base conditon, i.e., if number of islands are
# greater than 2, then return False
elif number_of_islands > 2:
return False
else:
m, n = len(island_grid), len(island_grid[0])
neighbors = [[1, 0], [0, 1], [-1, 0], [0, -1]]
# Simple traversing through all the blocked cells
for i in range(m):
for j in range(n):
curr_islands = set()
curr_ele = island_grid[i][j]
# Checking the neightbors of blocked cells
# adding them to a set, and then after the
# loop, we check if length of set >= 2
if curr_ele == -1:
for x, y in neighbors:
X, Y = i + x, j + y
# General base conditon
if 0 <= X < m and 0 <= Y < n:
# Adding elements to a set
if island_grid[X][Y] != -1:
curr_islands.add(island_grid[X][Y])
# If currently the islands connected to block cell
# is greater than or equal to 2, we return True
if len(curr_islands) >= 2:
return True
return False
# Driver code
grid = [[0, 1, 2, 0], [-1, -1, -1, -1], [-1, 5, 6, -1], [-1, 3, 4, -1]]
K = 4
number_of_islands = 0
# Unpacking the variables returning from the function
island_grid, number_of_islands, visited = generate_islands(grid, number_of_islands)
# Making a value set, for checking if all values in range
# [1,K] are visited or not.
value_set = set()
for x, y in visited:
value_set.add(grid[x][y])
# Print final ans
print(can_be_connected(island_grid, number_of_islands, value_set, K))

Output

Implementation in C++

#include <bits/stdc++.h>
#define ll long long int
using namespace std;
int number_of_islands = 0;
set<pair<int, int>> visited;
vector<vector<int>> generate_islands(vector<vector<int>> grid) {
vector<vector<int>> ans_grid = grid;
int m = grid.size();
int n = grid[0].size();
// For traversing through neighbors
vector<vector<int>> neighbors = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
// Traversing through the grid
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int curr_ele = grid[i][j];
// Starting the bfs at a digit between 1,K
if (curr_ele != 0 and curr_ele != -1 and visited.find({i, j}) == visited.end()) {
number_of_islands++;
visited.insert({i, j});
// Adding cordinates to the queue
deque<pair<int, int>> q = {{i, j}};
while (q.size()) {
// Breadth first search begins
pair<int, int> top = q[0];
q.pop_front();
int top_x = top.first;
int top_y = top.second;
// Changing the value of the newly formed grid
ans_grid[top_x][top_y] = number_of_islands;
// Traversing through the neighbors of x,y
for (int k = 0; k < 4; k++) {
int x = neighbors[k][0];
int y = neighbors[k][1];
int X = top_x + x;
int Y = top_y + y;
// Basic condition check
if (0 <= X and X < m and 0 <= Y and Y < n and grid[X][Y] != -1 and visited.find({X, Y}) == visited.end()) {
visited.insert({X, Y});
q.push_front({X, Y});
}
}
}
}
}
}
// Returns a island grid
return ans_grid;
}
/*
This function checks, if on removing at most one
blocked cell, can the points be connected or not
*/
bool can_be_connected(vector<vector<int>> island_grid, int K, set<int> value_set) {
/*
Initial check of all elements in range [1,K]
to be present and visited inside grid
*/
for (int i = 1; i < K + 1; i++) {
if (value_set.find(i) == value_set.end()) {
return false;
}
}
/*
Base conditon, i.e., if number of
island is 1, then return True
*/
if (number_of_islands == 1) {
return true;
}
/*
Base conditon, i.e., if number of islands are
greater than 2, then return False
*/
else if (number_of_islands > 2) {
return false;
}
else {
int m = island_grid.size();
int n = island_grid[0].size();
vector<vector<int>> neighbors = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
// Simple traversing through all the blocked cells
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
set<int> curr_islands;
int curr_ele = island_grid[i][j];
/*
Checking the neightbors of blocked cells
adding them to a set, and then after the
loop, we check if lenght of set >= 2
*/
if (curr_ele == -1) {
for (int k = 0; k < 4; k++) {
int x = neighbors[k][0];
int y = neighbors[k][1];
int X = i + x;
int Y = j + y;
// General base conditon
if (0 <= X and X < m and 0 <= Y and Y < n) {
// Adding elements to a set
if (island_grid[X][Y] != -1)
curr_islands.insert(island_grid[X][Y]);
}
}
/*
If currently the islands connected to block cell
is greater than or equal to 2, we return True
*/
if (curr_islands.size() >= 2){
return true;
}
}
}
}
}
return false;
}
int main()
{
vector<vector<int>> grid = {{0, 1, 2, 0}, {-1, -1, -1, -1}, {-1, 5, 6, -1}, {-1, 3, 4, -1}};
int K = 6;
// Unpacking the variables returning from the function
vector<vector<int>> island_grid = generate_islands(grid);
// Generating value_set
set<int> value_set;
for (auto &it : visited) {
value_set.insert(grid[it.first][it.second]);
}
// Final ans
if (can_be_connected(island_grid, K, value_set)) {
cout << "True" << endl;
}
else {
cout << "False" << endl;
}
return 0;
}

Output

Complexity Analysis

Let's analyze the complexity of the above codes. We performed BFS (Breadth First Search) on the above grid and have the following analysis.

Time Complexity

Since we are traversing the entire grid, which is of M*N dimensions, our time complexity reaches O(M*N).

Space Complexity

Since we are generating a new grid with labeled islands, our space complexity also reaches O(M*N), where M*N is the dimension of the grid.

Breadth First Search, or BFS, is a traversal algorithm used to traverse from a node in a graph to its children and from them to their children.

How is Breadth First Search implemented?

Breadth First Search is implemented with the help of a queue data structure, which follows the First In, First Out (FIFO) mechanism. We append the node to the queue and the top element's children to the queue before popping them out. Now the second element becomes the head element, and this goes on.

What are different types of traversals possible in a graph?

Two types of traversals are possible in a graph, namely, Breadth First Search and Depth First Search. The former follows the iterative method, while the latter follows the recursive approach.

How is BFS different from DFS?

BFS, or Breadth First Search, uses a queue as the data structure and stores the children in the queue by iterating over them. While DFS or Depth First Search uses a recursive form approach by calling the function again and again over the subtrees.

What are the applications of BFS?

BFS or Breadth First Search calculates the shortest distance between any two nodes. It is usually used to determine a tree's height or graph or find the shortest route between the root and any node.

Conclusion

So Ninjas!! This blog taught us about how we solved the above question using Breadth First Search (BFS) working. We also saw an application of queue data structure and how operations like push and pop work on it.

If you like this blog and are interested in more such content, visit our learning sections on queue here.

If you want to learn more about such topics, follow these links

But you have just started your learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview experiences, and interview bundles for placement preparations.

However, consider our paid courses to give your career an edge over others!