01 Matrix


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 topdown then bottomup. // while parsing topdown get min of top and left sides // while parsing bottomup 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[i1][j]<aux[i][j])) { aux[i][j] = aux[i1][j] + 1; } if ((j>0) && (aux[i][j1]<aux[i][j])) { aux[i][j] = aux[i][j1] + 1; } } } for (i=m1; i>=0; i) { for (j=n1; j>=0; j) { if (!mat[i][j]) { aux[i][j]=0; continue; } if ((i<m1) && (aux[i+1][j]<aux[i][j])) { aux[i][j] = aux[i+1][j] + 1; } if ((j<n1) && (aux[i][j+1]<aux[i][j])) { aux[i][j] = aux[i][j+1] + 1; } } } return aux; }
};

@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

@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.

@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/javadpsolutionomn.

There is another solution using "mergesort" similar approach with O(1) space, beats 97% of the submissions, must see!
https://discuss.leetcode.com/topic/106764/javao1spaceomnktimesimplesolutionandexplanationbeats97