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

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 

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

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.

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)

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)

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)

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.

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

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.

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

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

Run Code

Output

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

You can also try this code with Online Java Compiler

Run Code

Output

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:

• Find the number of connected grids of a given size in a 2D-Matrix
• Find the Number Of Islands
• Count the Number of Connected Components
• Number of Islands II
• The N - Queens Puzzle
• Rotting Oranges Problem
   

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!