01 Matrix


  • 0
    A

    Click here to see the full article post


  • 0
    N

    Dual parse solution!
    time complexity O(cr); space complexity O(cr).

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

        vector<vector<int>> aux ( m, vector<int> ( n, numeric_limits<int>::max() ) );
        
        // Dual parse solution first parse top-down then bottom-up.
        // while parsing top-down get min of top and left sides 
        // while parsing bottom-up get min of right and bottom sides.
        int i, j;
        for (i=0; i<m; i++) {
            for (j=0; j<n; j++) {
                if (!mat[i][j]) {
                    aux[i][j]=0;
                    continue;
                }
                if ((i>0) && (aux[i-1][j]<aux[i][j])) {
                    aux[i][j] = aux[i-1][j] + 1;
                }
                if ((j>0) && (aux[i][j-1]<aux[i][j])) {
                    aux[i][j] = aux[i][j-1] + 1;
                }
            }
        }
        
        for (i=m-1; i>=0; i--) {
            for (j=n-1; j>=0; j--) {
                if (!mat[i][j]) {
                    aux[i][j]=0;
                    continue;
                }
                if ((i<m-1) && (aux[i+1][j]<aux[i][j])) {
                    aux[i][j] = aux[i+1][j] + 1;
                }
                if ((j<n-1) && (aux[i][j+1]<aux[i][j])) {
                    aux[i][j] = aux[i][j+1] + 1;
                }
            }
        }
        return aux;
    }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.