Two Pass concise DP solution


  • 0
    Y
    public List<List<Integer>> updateMatrix(List<List<Integer>> matrix) {
            int row = matrix.size();
            int col = matrix.get(0).size();
            
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    if (matrix.get(i).get(j) == 0) continue;
                    int val = 10000;
                    if (i > 0) val = Math.min(val, matrix.get(i - 1).get(j) + 1);
                    if (j > 0) val = Math.min(val, matrix.get(i).get(j - 1) + 1);
                    matrix.get(i).set(j, val);
                }
            }
            
            for (int i = row - 1; i >= 0; i--) {
                for (int j = col - 1; j >= 0; j--) {
                    if (matrix.get(i).get(j) == 0) continue;
                    int val = matrix.get(i).get(j);
                    if (i < row - 1) val = Math.min(val, matrix.get(i + 1).get(j) + 1);
                    if (j < col - 1) val = Math.min(val, matrix.get(i).get(j + 1) + 1);
                    matrix.get(i).set(j, val);
                }
            }
            return matrix;
        }
    

Log in to reply
 

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