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

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.

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.

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