Check If Cells Numbered 1 to K In A Grid Can Be Connected After The Removal Of At most One Blocked Cell

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.

Input

grid = [ [0, 1, 2, 0], [-1, -1, -1, -1], [-1, 5, 6, -1], [-1, 3, 4, -1]] 
K = 6

Output

True

Explanation

As you can see, we have a grid, 

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.

Input

grid = [ [-1, -1, -1, 1], [-1, -1, -1, -1], [2, -1, -1, -1], [-1, -1, -1, -1] ] 
K = 2

Output

False

Explanation

As you can see, we have a grid, 

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

Input

grid = [ [0, 1, 2, 0], [-1, -1, -1, -1], [-1, 5, 6, -1], [-1, 3, 4, -1]] 
K = 6

Output

True

Explanation

Let's make a clear picture of the grid first.

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))

You can also try this code with Online Python Compiler

Run Code

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;
}

You can also try this code with Online C++ Compiler

Run Code

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. 

Check out this problem - Queue Implementation

Frequently Asked Questions

What is Breadth First Search?

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

• Breadth-First Search
• DFS Algorithm
• Traversals in Graph
   

Refer to our Guided Path to upskill yourself in DSA, Competitive Programming, JavaScript, System Design, and many more! If you want to test your competency in coding, check out the mock test series and participate in the contests hosted on Coding Ninjas Studio!

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!

Happy Learning!!