Easy Java DP solution


  • 0
    H
    public class Solution {
        public int[][] updateMatrix(int[][] matrix) {
            for(int i = 0; i < matrix.length; i++){
            	for(int j = 0; j < matrix[0].length; j++){
            		if(matrix[i][j] == 0) continue;
            		int up = i-1 >=0? (matrix[i-1][j]==Integer.MAX_VALUE?Integer.MAX_VALUE:matrix[i-1][j]+1):Integer.MAX_VALUE;
            		int left = j-1>=0?(matrix[i][j-1]==Integer.MAX_VALUE?Integer.MAX_VALUE:matrix[i][j-1]+1):Integer.MAX_VALUE;
            		matrix[i][j] = Math.min(up,left);
            	}
            }
    
    
            for(int i = matrix.length-1; i >= 0; i--){
            	for(int j = matrix[0].length-1; j>=0; j--){
            		if(matrix[i][j] == 0) continue;
            		int down = i+1<matrix.length? matrix[i+1][j]+1 : Integer.MAX_VALUE;
            		int right = j+1<matrix[0].length?matrix[i][j+1]+1:Integer.MAX_VALUE;
            		matrix[i][j] = Math.min(down,Math.min(right,matrix[i][j]));
            	}
            }
    
            return matrix;
        }
    }
    
    
    

Log in to reply
 

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