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 Matrix. Matrices 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.

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:

There are at-least 2*max(N, M) cells with value 0s.

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

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:

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

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.

Check for the number of zeroes greater than or equal to the 2*max(N, M) by calling the ‘check_zeroes’ function.

Maintain a ‘count’ variable to track the number of continuous blocks( i.e., connected components) of 0s.

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.

If the value of the total number of continuous blocks >= gcd(N, M), return “Yes”.

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

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

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

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.