# Java Solution 19ms beats 99.94%

• 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;
}
}
``````

• It seems that JAVA complier on LeetCode is full-optimized. When I change this solution into C++, it gets TLE. There might be a lot optimization on your zero-searching.

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