Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Understanding the Problem
3.
Intuition 
4.
Code
4.1.
Input
4.2.
Output
4.3.
Time Complexity
4.4.
Space Complexity
5.
Key Takeaways
Last Updated: Mar 27, 2024

Minimum Number of Operations Required to Set All Elements of a Binary Matrix

Author Saksham Gupta
0 upvote
Create a resume that lands you SDE interviews at MAANG
Speaker
Anubhav Sinha
SDE-2 @
12 Jun, 2024 @ 01:30 PM

Introduction

Any tech interview, be it be FAANG or that of any other top company, is incomplete without BFS. Therefore it's necessary that your basics and hands-on practice on BFS are rock solid. But you don't have to worry about any of it as Ninja is here to help you, and today, we will see one such important question, i.e.,  Minimum number of operations required to set all elements of a binary matrix.

Must Read, Array Implementation of Queue and  Rabin Karp Algorithm

Understanding the Problem

We have been given a binary matrix (containing only 0’s and 1’s) of size M * N. Our task is to find the minimum number of operations required to convert all 0’s to 1’s given that in each operation, all the 1’s convert their adjacent 0’s to 1’s.

Adjacent here refers to only top, bottom, left, and right elements, and not diagonal elements.

Let’s understand this by the following example.

‘MATRIX’ = 

0 1 1
0 0 0
0 0 0

The output will be 3

Explanation

Now ‘1’ at (0,1) index will first turn its adjacent 0’s to 1. Then we will have

1 1 1
0 1 0
0 0 0

Now ‘1’ at (1,1) index will turn it's adjacent 0’s to ‘1’. Then we will have

1 1 1
1 1 1
0 1 0

Finally ‘1’ at (2,1) will turn its adjacent ‘0’s to ‘1’

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

Intuition 

We know that whenever we want to find the shortest path from a certain source node to a certain destination (or more generally, the smallest number of steps to reach the end state from a given initial state), we have to use BFS. This question is also very similar to this thus the first thing that comes to our mind after reading the problem statement is BFS. 

But how?

Let’s have a look at it.

Firstly we will insert all the coordinates of 1’s of the matrix in a queue (queue is used for performing BFS). Then, as usual, BFS is performed. We will also maintain a variable, ‘OPERATION_COUNT’ initialized with zero. We will run a while loop till the queue becomes empty. Now inside it, we will run again a for loop for all elements present in the queue (i.e., size of the queue). This is because, at each operation (to change 0 to 1), Not only a single element but the complete matrix will change. Now inside this loop, we will first dequeue the topmost element of the queue and check its neighbors if they are 0. If they are 0, then we will change them to 1 (in the matrix) and push their coordinates to the queue (as they are also ‘1’ now). After this loop gets over, we will increase the ‘OPERATION_COUNT’ variable, which is going to store our final answer.

Now let us look at the above words put into code.

Code

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// Matrix to traverse over adjacent elements.
int adjacentElements[4][2] = {
                           {1, 0},
                           {-1, 0},
                           {0, 1},
                           {0, -1}
                           };

// Function to check whether a given set of 'R' and 'C' (row and col indices) are within the matrix.
bool isValid(int row, int col, int r, int c)
{

   return (r >= 0 && r < row && c >= 0 && c < col);
}

// Function that will return the minimum operation count.
int minOperations(int row, int col, vector<vector<int> > &matrix)
{
   // Queue of pair type (for vertices) to perform BFS.
   queue<pair<int, int> > q;

   // Pushing vertices of 1's in the queue.
   for (int i = 0; i < row; i++)
   {
       for (int j = 0; j < col; j++)
       {
           if (matrix[i][j] == 1)
               q.push(make_pair(i, j));
       }
   }

   // Variable holding our final answer.
   int operationCount = -1;

   // BFS.
   while (!q.empty())
   {
       int size = q.size();
       int count = 0;
       while (count < size)
       {
           pair<int, int> top = q.front();
           q.pop();

           // Traversing adjacent elements.
           for (int i = 0; i < 4; i++)
           {
               int r = top.first +
                       adjacentElements[i][0];
               int c = top.second +
                       adjacentElements[i][1];

               if (isValid(row, col, r, c) && matrix[r][c] == 0)
               {
                   // If it’s valid and '0', then we will convert it to 1 and then push its vertices to the queue.
                   q.push({r, c});
                   matrix[r][c] = 1;
               }
           }
           count++;
       }

       // Increase operation_count
       operationCount++;
   }

   return operationCount;
}

// Main function.
int main()
{
   // Taking user input.
   int m, n;
   cout << "Enter number of rows: ";
   cin >> m;
   cout << "Enter number of columns: ";
   cin >> n;
   cout << "Enter elements of matrix: " << endl;
   vector<vector<int> > matrix(m, vector<int>(n, 0));
   for (int i = 0; i < m; i++)
   {
       for (int j = 0; j < n; j++)
       {
           int x;
           cin >> x;
           matrix[i][j] = x;
       }
   }

   cout << "Minimum number of operations required to set all elements of a binary matrix is: ";
   cout << minOperations(m, n, matrix);
}


Input

Enter the number of rows: 3
Enter the number of columns: 3
Enter the elements of the matrix:
0 1 1
0 0 0
0 0 0

Output

Minimum number of operations required to set all elements of a binary matrix is : 3

Time Complexity

O(M * N), where ‘M’ is the number of rows and ‘N’ is the number of columns in the given matrix.

As we are traversing every element in the matrix only once and as there are a total of M * N elements, the time complexity is also O(M * N).

Space Complexity

O(M * N), where ‘M’ is the number of rows and ‘N’ is the number of columns in the given matrix. 

As we are using a queue to perform BFS whose size will be equal to M * N, in the worst case. Thus, the time complexity is O(M * N).

Key Takeaways

We saw how we could apply BFS to solve the problem ‘Minimum number of operations required to set all elements of a binary matrix’, which caused us O(M * N) time and O(M * N) space. Now, BFS is a wide as well as an important topic. Thus you should keep practicing till you master it. So what are you waiting for? Rush to our practice platform Coding Ninjas Studio to practice top problems such as Shortest Path In Binary MatrixCheck Permutation, etc, interview experiences, and many more. Till then, Happy Coding!

 

Live masterclass