9q3418

Concise blog, but I can't help

Too easy

class Solution {
public:
    vector<vector<int>> dp;
    vector<vector<int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    
    int dfs(vector<vector<int>>& grid, int i, int j) {
        if (grid[i][j] == 0) return 0;
        if (dp[i][j] != -1) return dp[i][j];
        
        int minDist = INT_MAX - 100000;
        for (auto dir : directions) {
            int x = i + dir[0];
            int y = j + dir[1];
            if (x >= 0 && y >= 0 && x < grid.size() && y < grid[0].size()) {
                minDist = min(minDist, dfs(grid, x, y) + 1);
            }
        }
        
        return dp[i][j] = minDist;
    }
    
    vector<vector<int>> updateMatrix(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        dp = vector<vector<int>>(n, vector<int>(m, -1));
        
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == 1) {
                    dfs(grid, i, j);
                } else {
                    dp[i][j] = 0;
                }
            }
        }
        
        return dp;
    }
};

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