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

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 nonzero entries is proportional to the number of 1entries. 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;
}