I don't know if LeetCode has some issues for this problem or not. This straight-forward brutal solution reaches the performance mentioned in the topic. I didn't search all the solutions in this problem. Since it beats 99.94%, I think I could just post it for review.

I use extra memory so that the input matrix array will stay untouched. If modification of the input array is allowed, I think this solution could also be done in place.

```
public class Solution {
public int[][] updateMatrix(int[][] matrix) {
int numRows = matrix.length;
if (numRows == 0)
return matrix;
int numCols = matrix[0].length;
if (numCols == 0)
return matrix;
int[][] ret = new int[numRows][numCols];
for (int i = 0; i < numRows; i++) {
for (int j = 0; j < numCols; j++) {
if (matrix[i][j] == 0) {
ret[i][j] = 0;
} else {
int up = i > 0 ? ret[i-1][j] : Integer.MAX_VALUE;
int left = j > 0 ? ret[i][j-1] : Integer.MAX_VALUE;
int min = Math.min(up, left);
if (min == 0) {
ret[i][j] = 1;
continue;
}
int val = searchForZero(matrix, i, j);
ret[i][j] = min == Integer.MAX_VALUE ? val : Math.min(val, min + 1);
}
}
}
return ret;
}
private int searchForZero(int[][] matrix, int x, int y) {
int numRows = matrix.length;
int numCols = matrix[0].length;
if (x == numRows - 1 && y == numCols - 1)
return Integer.MAX_VALUE;
int right = y < numCols - 1 ? matrix[x][y+1] : Integer.MAX_VALUE;
int down = x < numRows - 1 ? matrix[x+1][y] : Integer.MAX_VALUE;
if (right == 0 || down == 0)
return 1;
if (right != Integer.MAX_VALUE)
right = searchForZero(matrix, x, y + 1);
if (down != Integer.MAX_VALUE)
down = searchForZero(matrix, x + 1, y);
int ret = Math.min(right, down);
return ret == Integer.MAX_VALUE ? Integer.MAX_VALUE : ret + 1;
}
}
```