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

Run Code
### 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!