[BLOG] Untitled Post

untitled-post.md

title	location	images	tags	privacy	createdAt
Untitled Post	19.2053, 72.9481		blog quick-post	public	2025-10-08 21:49:14 UTC

https://leetcode.com/problems/01-matrix/

“Each cell’s distance depends on its four neighbors, but since we can’t know all neighbors’ values at once, we calculate in two sweeps. In the first pass (top-left → bottom-right), each cell checks its top and left neighbors because those are already processed. In the second pass (bottom-right → top-left), each cell checks its bottom and right neighbors. At every step, we update dist[i][j] = min(dist[i][j], neighbor + 1). This way, all cells gradually get the minimum distance to the nearest 0, even the (0,0) cell.”

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int m= mat.size();
        int n = mat[0].size();
        vector<vector<int>> dist(m, vector<int>(n, INT_MAX-10000));

        for(int i =0;i<m;i++){
          for(int j =0;j<n;j++){
            if(mat[i][j]==0){
                dist[i][j]=0;
            }else {
                if(i>0){
                    dist[i][j]=min(dist[i][j],dist[i-1][j]+1);
                }
                if(j>0){
                    dist[i][j]=min(dist[i][j],dist[i][j-1]+1);
                }
            }
         }  
         }

         for(int i=m-1;i>=0;i--){
            for(int j=n-1; j>=0;j--){
                if(i<m-1){
                    dist[i][j]= min(dist[i][j],dist[i+1][j]+1);
                }
                if(j<n-1){
                    dist[i][j]= min(dist[i][j],dist[i][j+1]+1);
                }
            }
         }

         return dist;
    }
};