# Java solution, time complexity O(n), no auxiliary space.

• Algorithm: Dynamic Programming
Time complexity is O(n), since I traverse the matrix twice.

public class Solution {
public int[][] updateMatrix(int[][] matrix) {
int rowL = matrix.length;
int colL = matrix[0].length;
int longer = Math.max(rowL, colL);
int[][] result = new int[rowL][colL];
fromUpLeftToRightDown(matrix, result, rowL, colL, longer);
fromRightDownToUpLeft(matrix, result, rowL, colL, longer);
return result;
}
private void fromUpLeftToRightDown(int[][]matrix, int[][]result, int rowL, int colL, int longer) {
for (int i = 0; i < rowL; i++) {
for (int j = 0; j < colL; j++) {
if (matrix[i][j] == 0) {
result[i][j] = 0;
} else if (i == 0 && j == 0) {
result[i][j] = longer;
} else if (i == 0) {
result[i][j] = 1 + result[i][j - 1];
} else if (j == 0) {
result[i][j] = 1 + result[i - 1][j];
} else {
result[i][j] = 1 + Math.min(result[i][j - 1], result[i - 1][j]);
}
}
}
}
private void fromRightDownToUpLeft(int[][]matrix, int[][]result, int rowL, int colL, int longer) {
for (int i = rowL - 1; i >= 0; i--) {
for (int j = colL - 1; j >= 0; j--) {
if (matrix[i][j] == 0 || (i == rowL - 1 && j == colL - 1)) {
continue;
} else if (i == rowL - 1) {
result[i][j] = Math.min(result[i][j], 1 + result[i][j + 1]);
} else if (j == colL - 1) {
result[i][j] = Math.min(result[i][j], 1 + result[i + 1][j]);
} else {
result[i][j] = Math.min(result[i][j], Math.min(1 + result[i][j + 1], 1 + result[i + 1][j]));
}
}
}
}
}

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