Java Solution 19ms beats 99.94%


  • 0
    B

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

  • 0
    N

    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.


Log in to reply
 

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