BFS
Intuition for the BFS is straightforward. We’ll perform BFS in the matrix. For this, we will first mark visited and unvisited cells. We will mark visited cells with 0 (Also, cells that contain 0 will be marked as zero as that is the minimum distance to other 0, and there is no need to visit them). Thus, cells containing 0 will be pushed in the queue as well as they are now visited, and cells containing 1 will be marked as -1. Now we will perform BFS until the queue is empty. We will pop an element from the queue (basically index of a cell) and will check for its adjacent elements. If it’s out of the boundary or if it’s visited, e’ll skip it. Otherwise, we will update it with the value of the current element (value at the cell that is popped) + 1.
Now things will become more clear from the code.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<vector< int> > updateMatrix(vector<vector< int> > &mat)
{
int m = mat.size();
int n = mat[0].size();
// To perform a search in adjacent directions.
vector<int> DIR = { 0, 1, 0, - 1, 0};
// Queue to perform BFS.
queue<pair<int, int> > q;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
// If 0, then we can mark it as visited.
if (mat[i][j] == 0)
{
q.push({i, j});
}
// Not visited.
else
mat[i][j] = - 1;
}
while (q.size() != 0)
{
int r = q.front().first;
int c = q.front().second;
q.pop();
for (int i = 0; i < 4; ++i)
{
// Checking if it's within the boundary.
int nr = r + DIR[i], nc = c + DIR[i + 1];
if (nr < 0 || nr == m || nc < 0 || nc == n || mat[nr][nc] != - 1)
continue;
// Updating value according to the algorithm.
mat[nr][nc] = mat[r][c] + 1;
q.push({nr, nc});
}
}
return mat;
}
int main()
{
// Taking user input.
int m, n;
cin >> m >> n;
vector<vector< int> > matrix(m, vector<int>(n, 0));
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
cin >> matrix[i][j];
}
}
// Calling the function, 'updateMatrix()'.
matrix = updateMatrix(matrix);
// Printing the final matrix.
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
cout << matrix[i][j] << " ";
}
cout << '\n';
}
return 0;
}
You can also try this code with Online C++ Compiler
Input
3 3
0 1 1
0 1 1
0 1 1
Output
0 1 2
0 1 2
0 1 2
Time Complexity
O(M * N), where ‘M’ is the number of rows and ‘N’ is the number of columns in the matrix.
As we are traversing each element in the matrix only once and there are M * N elements in the matrix, the time complexity is O(M * N)
Space Complexity
O(M * N), where ‘M’ is the number of rows and ‘N’ is the number of columns in the matrix.
This is because we are using an extra queue to perform BFS which will store a total of M * N elements. Thus taking the space complexity to O(M * N).
Now we are using extra space for the queue to perform BFS, and we surely can reduce it by performing in-place operations. But how? Let’s see.
Dynamic Programming
Now for DP, we will make use of cells that are being already processed, so we will not pick up cells containing ‘0’ as they can be initialized to 0 (which means they are visited). But how are we going to DP here?
We know that adjacent cells account for only 4 directions, i.e., top, bottom, left, and right; thus, we can divide the problem into two parts.
- In the first part, we will move only 2 directions which are left and top. Then we iterate cells from top to bottom, and from left to right, Basically, we will only calculate the distance of a cell-based only on its left and top neighbors.
- In the second part, we will move only 2 directions which are right and bottom. Then, we iterate cells from bottom to top, and from right to left, Basically, we will update the distance of a cell-based only on its right and bottom neighbors.
Finally, we can club the answer from both the steps to reach our final answer.
Refer to the following image for a better understanding.
We can see that in the first image we are computing distance from the cell’s top and left neighbors.
Whereas in the second image we are computing distance from a cell’s bottom and right neighbors.
Now things will become more clear from the code.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<vector< int> > updateMatrix(vector<vector< int> > &mat)
{
// The distance of cells is up to (M+N)
int m = mat.size(), n = mat[0].size(), boundary = m + n;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
// If it''s visited, then skip.
if (mat[i][j] == 0)
continue;
// Initializing with maximum possible value.
int top = m + n, left = m + n;
// If it's within boundaries.
if (j - 1 >= 0)
left = mat[i][j - 1];
if (i - 1 >= 0)
top = mat[i - 1][j];
// Filling the minimum value out of the two directions.
mat[i][j] = min(top, left) + 1;
}
}
for (int i = m - 1; i >= 0; i--)
{
for (int j = n - 1; j >= 0; j--)
{
// If it's visited, then skip.
if (mat[i][j] == 0)
continue;
// Initializing with maximum possible value.
int bottom = m + n, right = m + n;
// If it's. Close within boundaries.
if (i + 1 < m)
bottom = mat[i + 1][j];
if (j + 1 < n)
right = mat[i][j + 1];
// Filling the minimum value out of the two directions.
mat[i][j] = min(mat[i][j], min(bottom, right) + 1);
}
}
return mat;
}
int main()
{
// Taking user input
int m, n;
cin >> m >> n;
vector<vector< int> > matrix(m, vector<int>(n, 0));
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
cin >> matrix[i][j];
}
}
// Calling the function, 'updateMatrix()'.
matrix = updateMatrix(matrix);
// Printing the final matrix.
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
cout << matrix[i][j] << “ “;
}
cout << ‘\n’;
}
return 0;
}
Input
3 3
0 1 1
0 1 1
0 1 1
Output
0 1 2
0 1 2
0 1 2
Time Complexity
O(M * N), where ‘M’ is the number of rows and ‘N’ is the number of columns in the matrix.
As we are traversing each element in the matrix once, and there are M * N elements in the matrix. Thus we will be traversing over a total of M * N elements and therefore the complexity is O(M * N).
Space Complexity
O(1).
We are not using any extra space.
Key Takeaways
We saw how we solved the problem 0 1 matrix from BFS and then optimized it using DP. Now, understanding a new concept always makes one excited, and this excitement leads to learning more concepts. We are here to help you with that too. Close your eyes and click on Coding Ninjas Studio to practice top problems like 01 matrix, Set Matrix zeros, attempt mock tests, read interview experiences, and many more. Till then, Happy Coding!
116+ registered 