# JAVA DP solution 41ms with O(1) Space,O(m*n) time,with two sweep

• ``````//because of the max number of the element is 10000 so the dp[0][0] = 10000
// dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1
public List<List<Integer>> updateMatrix(List<List<Integer>> matrix) {
if(matrix.size() == 0) {
return matrix;
}
int a = matrix.size(), b = matrix.get(0).size();
int MAX =10000;
for (int i = 0 ; i< a; i ++) {
List<Integer> l = matrix.get(i);
for (int j = 0; j < b; j ++) {
if (l.get(j) == 0) {
continue;
}
if (i + 1 < a && matrix.get(i + 1).get(j) == 0) {
l.set(j, 1);
continue;
}
if (j + 1 < b && matrix.get(i).get(j + 1) == 0) {
l.set(j,1);
continue;
}
if (i - 1 >= 0 && j - 1 >= 0){
l.set(j,Math.min(matrix.get(i - 1).get(j), l.get(j - 1)) + 1);
}else if (i - 1 >= 0) {
l.set(j,matrix.get(i - 1).get(j) + 1);
}else if (j - 1 >= 0) {
l.set(j,l.get(j - 1) + 1);
}else {
l.set(j,MAX);
}
}
}
//dp[i][j] = Math.min(dp[i][j], Math.min(dp[i + 1][j], dp[i][j + 1]))
for (int i = a - 1; i >= 0; i --) {
List<Integer> l = matrix.get(i);
for (int j = b - 1; j >= 0; j --){
int min = l.get(j);
if (min == 1 || min == 0 ) {
continue;
}
if (i + 1 < a && j + 1 < b) {
min = Math.min(min, Math.min(matrix.get(i + 1).get(j), l.get(j + 1)) + 1);
}else if (i + 1 < a) {
min = Math.min(min ,matrix.get(i + 1).get(j) + 1);
}else if (j + 1 < b) {
min = Math.min(min ,l.get(j + 1) + 1);
}else {
continue;
}
l.set(j,min);
}
}
return matrix;
}
``````

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