JAVA DP solution 41ms with O(1) Space,O(m*n) time,with two sweep


  • 0
    T
    //because of the max number of the element is 10000 so the dp[0][0] = 10000
    // dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1
        public List<List<Integer>> updateMatrix(List<List<Integer>> matrix) {
            if(matrix.size() == 0) {
                return matrix;
            }
            int a = matrix.size(), b = matrix.get(0).size();
            int MAX =10000;
            for (int i = 0 ; i< a; i ++) {
                List<Integer> l = matrix.get(i);
                for (int j = 0; j < b; j ++) {
                    if (l.get(j) == 0) {
                        continue;
                    }
                    if (i + 1 < a && matrix.get(i + 1).get(j) == 0) {
                        l.set(j, 1);
                        continue;
                    }
                    if (j + 1 < b && matrix.get(i).get(j + 1) == 0) {
                        l.set(j,1);
                        continue;
                    }
                    if (i - 1 >= 0 && j - 1 >= 0){
                        l.set(j,Math.min(matrix.get(i - 1).get(j), l.get(j - 1)) + 1);
                    }else if (i - 1 >= 0) {
                        l.set(j,matrix.get(i - 1).get(j) + 1);
                    }else if (j - 1 >= 0) {
                        l.set(j,l.get(j - 1) + 1);
                    }else {
                        l.set(j,MAX);
                    }
                 }
            }
    //dp[i][j] = Math.min(dp[i][j], Math.min(dp[i + 1][j], dp[i][j + 1]))
            for (int i = a - 1; i >= 0; i --) {
                List<Integer> l = matrix.get(i);
                for (int j = b - 1; j >= 0; j --){
                    int min = l.get(j);
                    if (min == 1 || min == 0 ) {
                        continue;
                    }
                    if (i + 1 < a && j + 1 < b) {
                        min = Math.min(min, Math.min(matrix.get(i + 1).get(j), l.get(j + 1)) + 1);
                    }else if (i + 1 < a) {
                        min = Math.min(min ,matrix.get(i + 1).get(j) + 1);
                    }else if (j + 1 < b) {
                        min = Math.min(min ,l.get(j + 1) + 1);
                    }else {
                        continue;
                    }
                    l.set(j,min);
                }
            }
            return matrix;
        }
    

Log in to reply
 

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