**Given an m x n binary matrix matrix, return the distance of the nearest 0 for each cell.** **The distance between two adjacent cells is 1.**

**Code:**

```
class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& grid) {
int n = grid.size();
int m = grid[0].size();
vector<vector<int>> dp(n, vector<int>(m, INT_MAX - 100000));
// First pass: Top-left to bottom-right
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (grid[i][j] == 0) {
dp[i][j] = 0;
} else {
if (i > 0) dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1);
if (j > 0) dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1);
}
}
}
// Second pass: Bottom-right to top-left
for (int i = n - 1; i >= 0; --i) {
for (int j = m - 1; j >= 0; --j) {
if (i < n - 1) dp[i][j] = min(dp[i][j], dp[i + 1][j] + 1);
if (j < m - 1) dp[i][j] = min(dp[i][j], dp[i][j + 1] + 1);
}
}
return dp;
}
};
```

Queries:

**Q1**

Why does it work ? I understood a little by doing some dry runs but still not able to get the complete feel. If you know any other similar problem, please do share it.

**Q2**

I also want to know if there exists more unique/different dp traversals like these to solve particular problems. Eg. maybe a clockwise and anticlockwise traversal.

**Q3**

I also couldn't write the memoized recursive solution, If you can help me with that, that'd be of great help.

Thanks for your time.

9q3418

wtf

Concise blog, but I can't help

Too easy

That would lead to stack overflow due to infinite recursive calls.

Yup, it's happening. I don't understand why

Got it! can bfs help minimize these recursive calls?

yeah bfs does work here, but I was more curious on how to implement recursive dp.

why not just use multi-source bfs? With it, you will have only 1 bfs call

I could explain one possible solution, which uses bfs instead of dfs, which you probably meant when saying you wanted to write a recursive solution

You could use multi-source 2D-bfs. You create queue, in which you put all zeros with 0 as a distance. Then you write regular bfs, where for every visited point you save its distance and mark it as viewed. Total complexity would be O(n * m)

In the first pass, the dp is set such that it is the minimum distance of 0 from the cell using only up and left directions.

In the second pass, the dp will also consider the down and right direction for getting the zero. It is clear that if for some cell the shortest path to the nearest zero is only using up-left or down-right directions then it will give the correct answer.

For up-right and down-left case, we could prove by induction that the dp will store the correct answer. Clearly if there is some cell where only up path leads to nearest zero, in this cell we can claim that it takes up-right direction path to find the nearest zero(even if the right path does not exist). Similar argument goes with down-left case.

If we assume that all the visited cells have taken up-right and down-left path into consideration then the next cell that is to be visited will consider its right and down neighbour and eventually consider the down-left or up-right path. Hence by induction the dp array will store minimum of all types of paths to nearest zero.

why not just multisource bfs from all the 0s