Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Input
2.2.
Output
2.3.
Explanation
3.
DFS Approach
3.1.
Algorithm
3.2.
Dry Run
3.3.
Implementation in C++
3.3.1.
Output
3.4.
Implementation in Java
3.4.1.
Output
3.5.
Time Complexity
3.6.
Space Complexity
4.
Frequently Asked Questions
4.1.
What is a binary matrix?
4.2.
What do you mean by depth-first search?
4.3.
What do you mean by breadth-first search?
4.4.
What do you mean by gcd of two numbers?
4.5.
What are the advantages of the depth-first search traversal technique?
4.6.
What are the applications of depth-first search traversal techniques?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Check if there are at least T continuous blocks of 0s or not in a Binary Matrix

Author Sahil Setia
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

Hey Ninjas! In this blog, we will discuss a problem based on a Binary matrix. A matrix in which all the elements have a value of either 0 or 1 is known as a binary matrix. It is also called a Logical or Boolean MatrixMatrices are one of the most important and often-asked data structures in programming contests and technical interviews. There are various standard matrix problems and techniques.

Introduction image

This blog will discuss the approach to check if there are at least T continuous blocks of 0s or not in a binary matrix. We will use the depth-first search approach to find the solution to our problem. Let’s take a brief look at the problem statement once again.

Problem Statement

You are given a binary matrix (with values 0 or 1) with N rows and M columns. The task is to print output as “Yes” if both the below-given conditions are satisfied:

  1. There are at-least 2*max(N, M) cells with value 0s.
  2. There exist at least T continuous blocks of 0s where T is the GCD(greatest common divisor) of N and M. 
     

Otherwise, print “No.”

Note: A continuous span of cells from row to row, column to column, or diagonally is referred to as a continuous block.

Input

N=3, M=3

Input image

Output

No

Explanation

The total number of cells with value zero equals 6 >= 2*max(3,3). Hence, our condition is satisfied.

Value of T = gcd(3,3) = 3.

Hence, there must be at least T continuous blocks of zeroes.

The total number of continuous blocks in our grid= 1 as shown below:

Output image

Hence, our second condition is unsatisfied, so our output will be “No”.

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

DFS Approach

The concept is to count how many cells have a value of 0, and if that meets the requirement, identify the greatest common divisor of M and N, then use a depth-first search to determine how many continuous blocks( i.e., connected components) are present with a value of zero.

Algorithm

  1. Call the ‘check’ function for the corresponding matrix, for which we need to check if there are at least T continuous blocks of 0s or not.
     
  2. Check for the number of zeroes greater than or equal to the 2*max(N, M) by calling the ‘check_zeroes’ function.
     
  3. Maintain a ‘count’ variable to track the number of continuous blocks( i.e., connected components) of 0s.
     
  4. Using two for loops, iterate over the matrix, for each row from 0 to N-1 and for each column from 0 to M-1. For every element which is 0, increase the count and apply DFS Algorithm(depth-first search ) to cover all the cells that lie in the same connected component as the current one.
     
  5. If the value of the total number of continuous blocks >= gcd(N, M), return “Yes”.
     
  6. Otherwise, return “No” at the end.

Dry Run

  • Input matrix 
Dry run image 1

Initially, we will count the total number of zeroes in our matrix and compare it with the value 2 * max(N, M).

Dry run image 2

Our total number of zeroes in the matrix is equal to the value 2 * max(N, M). Therefore, the first condition of the problem statement is satisfied.

Now, let’s move on to the second condition to find the continuous blocks in our 2-d matrix with the value 0.

  • Our dfs traversal will begin with cell (0,0) as it is the first cell with value 0 and is not visited.
Dry run image 3

Now, our cell (0,0) is visited and we will look in all possible directions of this cell row-wise, column-wise and diagonal-wise and look for the next unvisited cell with a value ‘0’ and perform dfs on that cell.

Cell (0,0) diagonal’s cell – > Cell (1,1)

Dry run image 4

Now, our cell (1,1) is visited, and we will look in all possible directions of this cell row-wise, column-wise and diagonal-wise and look for the next unvisited cell and perform dfs on that cell.

Cell (1,1) right direction column’s cell – > Cell (1,2)

Dry run image 5

Now, our cell (1,2) is visited, and we will look in all possible directions of this cell row-wise, column-wise and diagonal-wise and look for the next unvisited cell and perform dfs on that cell.

Cell (1,2) upper direction row’s cell – > Cell (0,2)

Dry run image 6

Now, our cell (0,2) is visited, and we will look in all possible directions of this cell row-wise, column-wise and diagonal-wise and look for the next unvisited cell and perform dfs on that cell.

Dry run image 7

Note: Cell(0,2) has no unvisited cell; hence, we have reached a deeper node, and now backtracking of previous cells will occur.

The previous cell (1,2) will now reach cell (2,2).

Dry run image 8

Cell (2,2) has no unvisited cells, so we will backtrack to its previous node (1,2).

Cell (1,2) also has no unvisited cells, so we will backtrack to its previous node (1,1).

Currently, our cell (1,1) bottom left diagonal element is visited with coordinates (2,0), and all zeroes in the matrix are visited.

Dry run image 8

Observation: Here, we visited all the zeroes in the matrix in only a single dfs traversal. Hence, the connected components in the given matrix are one.

The total number of continuous blocks = 1

Value of T = gcd(N, M) = gcd(3,3) = 3.

Hence, we can see that the total number of continuous blocks is less than the value of T.

So, our second condition is unsatisfactory, and the output is “No.”

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

// Direction vector to iterate in all directions- row, col, diagonal
int dir[8][2]={{ 0, 1 }, { 0, -1 }, { -1, 0 },{ 1, 0 }, { 1, 1 }, { -1, -1 }, { -1, 1 }, { 1, -1 }};

bool valid_index(int row,int col, int n,int m){
    
    if(row<0 || col<0 || row>=n || col>=m){
        return 0;
    }
    return 1;
}

// Function to perform DFS.
void dfs(vector<vector<int> > matrix, int n, int m, int row, int col, vector<vector<bool> >& visited){    

    // Checking for invalid index, already visited and cell with value 1
    if (!valid_index(row,col,n,m) || visited[row][col] || matrix[row][col]){
        return ;
    }
    visited[row][col] = true;

    for( int i=0;i<8;i++){
        int x = row + dir[i][0];
        int y = col + dir[i][1];
        dfs( matrix, n, m, x, y, visited);
    }
}

bool check_zeroes(int n,int m, vector <vector <int>>& matrix){
    
    // For storing the total count of 0's
    int total=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            
            if(matrix[i][j]==0)
            ++total;
        }
    }
    
    if(total>=2*max(n,m)){
        return 1;
    }
    else{
        return 0;
    }
}

string check(int n, int m, vector<vector<int> >& matrix){
    
    // Checking for total number of zeroes
    if(check_zeroes(n,m,matrix)==false){
        return "No";
    }
    vector<vector<bool>> visited(n, vector<bool>(m,false));
    
    // Function for calculating gcd
    int T = __gcd(n, m);
    
    // Count for storing continous blocks count
    int count = 0;

    // Iterate over the matrix for DFS.
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            
            if (matrix[i][j] == 0 && visited[i][j] == false) {
                ++count;
                
                // Calling the DFS
                dfs(matrix, n, m, i, j, visited);
            }
        }
    }
    
    // Check gcd condition.
    if( count >= T)
        return "Yes";
    
    return "No";
}

int main(){    
    
    // Size of the matrix
    int n = 3, m = 3;     

    // The elements of the matrix
    vector<vector<int>> matrix = { {0, 1, 0}, {1, 0, 0}, {0, 1, 0}};
    
    // Calling the check function
    cout<<check(n, m, matrix);

    return 0;
}

 

Output

Output image 2

Implementation in Java

public class MyClass {
    
    // Function which returns the GCD of a and b
    static int gcd(int a, int b){
        // base condition
        if (b == 0)
            return a;
            
        else
            return gcd(b, a % b);
    }
    
    // Direction vector to iterate in all directions- row, col, diagonal
    static int dir[][]={{ 0, 1 }, { 0, -1 }, { -1, 0 },{ 1, 0 }, { 1, 1 }, { -1, -1 }, { -1, 1 }, { 1, -1 }};

    static boolean valid_index(int row,int col, int n,int m){
        if(row<0 || col<0 || row>=n || col>=m){
            return false;
        }
        return true;
    }
    
    // Function for DFS call
    static void dfs(int [][] matrix,int n,int m,int row,int col,boolean [][] visited){

        // Checking for invalid index, already visited and cell with value 1
        if (valid_index(row,col,n,m)==false || visited[row][col]==true || matrix[row][col]==1)
            return ;
        visited[row][col] = true;   
    
        for( int i=0;i<8;i++){
            int x = row + dir[i][0];
            int y = col + dir[i][1];
            dfs( matrix, n, m, x, y, visited);
        }
    }
    
    // Function for checkinng total count of zeroes
    static boolean check_zeroes(int n,int m,int matrix[][]){

        // For storing the total count of 0's
        int total=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                
                if(matrix[i][j]==0)
                ++total;
            }
        }
        
        if(total>=2*Math.max(n,m)){
            return true;
        }
        else{
            return false;
        }
    }
    
    // Check function
    static boolean check(int n,int m,int matrix[][]){
        
        // Checking for total number of zeroes
        if(check_zeroes(n,m,matrix)==false){
            return false;
        }
        
        // array for dfs traversal
        boolean [][] visited;
        visited = new boolean[n][m];

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                visited[i][j]=false;
            }
        }
        
        // Function for calculating gcd
        int T = gcd(n, m);
        
        // Count for storing continous blocks count
        int count = 0;
    
        // Iterate over the matrix for DFS.
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                
                if (matrix[i][j] == 0 && visited[i][j] == false) {
                    ++count;
                    
                    // Calling the DFS
                    dfs(matrix, n, m, i, j, visited);
                }
            }
        }
        
        // Check gcd condition.
        if( count >= T){
            return true;
        }
       
        return false;
        
    }
    public static void main(String args[]) {
        
        // Size of the matrix
        int n = 3, m = 3;     
        
        // The elements of the matrix
        int[][] matrix = { {0, 1, 0}, {1, 0, 0}, {0, 1, 0}};
        
        // Calling the check function
        if(check(n,m,matrix)==true)
        System.out.println("Yes");
        else
        System.out.println("No");
    }
}

 

Output

Output image 2

Time Complexity

O(N*M) where ‘N’= total number of rows in the matrix and ‘M’= the total number of columns in the matrix.

Explanation: For counting the total number of zeroes, we require two loops, therefore, O(N*M). For dfs traversal, in the worst case, all matrix elements will be in a single continuous block; therefore, O(N*M) is required for dfs traversal. Hence, the overall time complexity of the solution is O(N*M).

Space Complexity

O(N*M) where ‘N’= the total number of rows in the matrix and ‘M’= the total number of columns.

Explanation: We created a 2-D matrix visited of size N*M and, of course, our input matrix with size N*M, thus, giving a net space complexity of O(N*M).\

Check out this problem - Matrix Median

Must Read Static Blocks In Java.

Frequently Asked Questions

What is a binary matrix?

A binary matrix is one in which all the elements are 0 or 1. It is also called a Logical or Boolean Matrix.

What do you mean by depth-first search?

A tree data structure or a graph's entire vertex set can be searched using a recursive approach by the dfs algorithm. Beginning with the first node of graph G, the depth-first search (DFS) algorithm digs down until it reaches the target node, also known as the leaf node, with no children.

What do you mean by breadth-first search?

A graph traversal algorithm called breadth-first search investigates every node in the graph, starting with the root node. Next, it chooses the closest node and investigates every new unvisited node.

What do you mean by gcd of two numbers?

GCD stands for greatest common divisor, which means the most significant number that divides both numbers evenly, i.e., without leaving any remainder.

What are the advantages of the depth-first search traversal technique?

More quickly reaches the goal node than other methods like BFS. Less memory is used because only the stack of nodes that lie on the path from the root node to the current node is stored.

What are the applications of depth-first search traversal techniques?

One may solve one-solution puzzles like mazes and sudokus, scheduling issues, graph cycle identification, and topological sorting with depth-first search.

Conclusion

In this blog, we discussed a problem based on a binary matrix and used the depth-first search(dfs) concept between two nodes having the same value in a Binary Tree. We learned to modify the depth-first search traversal to implement the idea in 2-D matrices and solved our problem to check if there are at least T continuous blocks of 0s or not in a binary matrix. It is usual to modify well-known algorithms to serve our purpose.

Recommended Reading:

Also, check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, and System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy Coding!

Previous article
DFS using Adjacency Matrix
Next article
Find Regions with Most Common Region Size in a Given Boolean Matrix
Live masterclass