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!

  • 0
    W

    Can you please explain in more detail how the approach #2 with BFS starting from destination cells (value 0 cells) is O(r * c) time complexity? It is not clear to me. I don't need formal proof just better explanation.


  • 0
    Z

    I think for approach #2, you actually could update the matrix directly


  • 0
    H

    It seems the time complexity is at least O(r * c), since the matrix should be scanned. However, the complexity of the calculation part for the non-zero entries is proportional to the number of 1-entries. The following algorithm is similar to BFS...

    typedef struct Pair_
    {
    int i;
    int j;
    } Pair;

    int mat_get_dis(int **B, int i, int j, int r, int c, int round)
    {
    int k = -1, d = -1;

    if (B[i][j] >= 0) {
        return B[i][j];
    }
    
    /* dis: up */
    if (i > 0 && B[i - 1][j] >= 0) {
        k = B[i - 1][j];
    
        if (d < 0) {
            d = k;
        }
        else if (d >= 0 && d > k) {
            d = k;
        }
    }
    
    /* dis: down */
    if (i < r - 1  && B[i + 1][j] >= 0) {
        k = B[i + 1][j];
    
        if (d < 0) {
            d = k;
        }
        else if (d >= 0 && d > k) {
            d = k;
        }
    }
    
    /* dis: left */
    if (j > 0 && B[i][j - 1] >= 0) {
        k = B[i][j - 1];
    
        if (d < 0) {
            d = k;
        }
        else if (d >= 0 && d > k) {
            d = k;
        }
    }
    
    /* dis: right */
    if (j < c - 1 && B[i][j + 1] >= 0) {
        k = B[i][j + 1];
    
        if (d < 0) {
            d = k;
        }
        else if (d >= 0 && d > k) {
            d = k;
        }
    }
    
    if (d >= 0) {
        if (d <= round) {
            B[i][j] = 1 + d;
        }
        else {
            d = -1;
        }
    }
    
    return d;
    

    }

    int ** mat_dis(int **A, int r, int c)
    {
    int **B;
    int i, j;
    Pair td; / to be determined */
    int s, m, d, round;

    assert(A != NULL);
    assert(r > 0);
    assert(c > 0);
    
    B = malloc(sizeof(*B) * r);
    assert(B != NULL);
    
    for (i = 0; i < r; i++) {
        B[i] = malloc(sizeof(int) * c);
        assert(B[i] != NULL);
    }
    
    /* aux mem */
    td = malloc(sizeof(*td) * r * c);
    
    s = 0;
    for (i = 0; i < r; i++) {
        for (j = 0; j < c; j++) {
            if (A[i][j] == 0) {
                B[i][j] = 0;
            }
            else {
                B[i][j] = -1;
    
                td[s].i = i;
                td[s].j = j;
    
                s++;
            }
        }
    }
    
    /* width first search */
    round = 0;
    while (s > 0) {
        m = 0;
        for (i = 0; i < s; i++) {
            d = mat_get_dis(B, td[i].i, td[i].j, r, c, round);
    
            if (d < 0) {
                td[m].i =  td[i].i;
                td[m].j =  td[i].j;
                m++;
            }
        }
    
        s = m;
        round += 1;
    }
    
    free(td);
    
    return B;
    

    }


Log in to reply
 

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