# JAVA DP solution, O(N*M) time double traverse matrix; 67ms.

• Algo thinking:
dp[i][j] represents updated matrix value at [i, j];
double traverse:
(1) 1st traverse: from upper left conner to bottom right conner
(2) 2nd traverse: from bottom right conner to upper left conner

time = O(N*M), space = O(1)

``````public List<List<Integer>> updateMatrix(List<List<Integer>> matrix) {

int n = matrix.size();
int m = matrix.get(0).size();

List<List<Integer>> updatedMatrix = new ArrayList<List<Integer>>();
int[][] dir = new int[][]{{0, -1}, {-1, 0}};
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (matrix.get(i).get(j) == 0) {
} else {
int dist = Integer.MAX_VALUE;
for (int[] d: dir) {
int newI = i + d[0];
int newJ = j + d[1];
if (newI < 0 || newJ < 0 || updatedMatrix.get(newI).get(newJ) == Integer.MAX_VALUE) continue;
dist = Math.min(dist, 1 + updatedMatrix.get(newI).get(newJ));
}
}
}
}

dir = new int[][]{{0, 1}, {1, 0}};
for (int i = n - 1; i >= 0; i--) {
for (int j = m - 1; j >= 0; j--) {
if (matrix.get(i).get(j) != 0) {
int dist = updatedMatrix.get(i).get(j);
for (int[] d: dir) {
int newI = i + d[0];
int newJ = j + d[1];
if (newI >= n || newJ >= m) continue;
dist = Math.min(dist, 1 + updatedMatrix.get(newI).get(newJ));
}
updatedMatrix.get(i).set(j, dist);
}
}
}

return updatedMatrix;
}``````

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