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

You can also try this code with Online C++ Compiler
Run Code
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 Matrix, Check Permutation, etc, interview experiences, and many more. Till then, Happy Coding!