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

    };


  • 0
    S

    @abhinavbansal0
    Hi,

    Could you tell me that why MAX_VALUE need to minus 100000 in the solution of DP?
    I got minus min value in my Java solution. I add MAX_VALUE - 10000 while initialization then it corrected. But I don't know why.

    Many thanks


  • 0
    B

    @seanyang929 If you take MAX_VALUE there then when we add 1 in that then due to overflow in the int value it will become MIN_VALUE.


  • 0
    M

    @seanyang929 Because when you do the dist[i - 1][j] + 1 or dist[i][j - 1] + 1, overflow could happen because the number in dist cell could be MAX_VALUE. Actually, I don't think minus 100000 is a good idea. It assumes that the longest distance is 100000. Indeed, what we should do is to check whether overflow happens. You can do it by minus because the matrix is not that large. You can see what I did in https://discuss.leetcode.com/topic/106622/java-dp-solution-o-mn.


  • 0
    C

    It is great solution. And I am confused about why need initial a matrix with MAX_VALUE? Such as if element is 1, put 1 as MAX_VALUE into matrix.


  • 0
    Y

    There is another solution using "merge-sort" similar approach with O(1) space, beats 97% of the submissions, must see!
    https://discuss.leetcode.com/topic/106764/java-o-1-space-o-mnk-time-simple-solution-and-explanation-beats-97


  • 0
    R
    This post is deleted!

Log in to reply
 

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