Java solution with int[][] 2 pass, easy to understand


  • 0
    S
    public class Solution {
        public List<List<Integer>> updateMatrix(List<List<Integer>> matrix) {
            int m = matrix.size();
            int n = matrix.get(0).size();
            int[][] dp = new int[m][n];
            int[][] mat = new int[m][n];
            for (int i = 0; i < m; i++){
                for (int j =0; j < n; j++){
                    dp[i][j] = Integer.MAX_VALUE;
                    mat[i][j] = matrix.get(i).get(j);
                }
            }
            
            for (int i =0; i < m; i++){
                for (int j =0; j < n; j++){
                    int left = Integer.MAX_VALUE;
                    int top = Integer.MAX_VALUE;
                    if (mat[i][j] == 0){
                        dp[i][j] = 0;
                        continue;
                    }
                    if (i-1 >=0 && dp[i-1][j] != Integer.MAX_VALUE){
                        left = dp[i-1][j];
                    }
                    if (j-1 >=0 && dp[i][j-1] != Integer.MAX_VALUE){
                        top = dp[i][j-1];
                    }
                    if (left == top && top == Integer.MAX_VALUE)
                        dp[i][j] = Integer.MAX_VALUE;
                    else {
                        dp[i][j] = Math.min(left, top) + 1;                    
                    }
                }
            }
            
            // go backward
            for (int i = m-1; i >= 0; i--){
                for (int j = n - 1; j >= 0; j --){
                    int right = Integer.MAX_VALUE;
                    int down = Integer.MAX_VALUE;
                    if (mat[i][j] == 0){
                        dp[i][j] = 0;
                        continue;
                    }
                    if (i + 1 <= m-1 && dp[i+1][j] != Integer.MAX_VALUE){
                        right = dp[i+1][j];
                    }
                    if (j + 1 <= n - 1 && dp[i][j+1] != Integer.MAX_VALUE){
                        down = dp[i][j+1];
                    }
                    if (right == down && down == Integer.MAX_VALUE)
                        dp[i][j] = Math.min(dp[i][j], Integer.MAX_VALUE);
                    else 
                        dp[i][j] = Math.min(dp[i][j], Math.min(right, down) + 1);
                }
            }
            List<List<Integer>> result = new ArrayList<>();
            for (int i =0; i < m; i++){
                List<Integer> temp = new ArrayList<>();
                for (int j =0; j < n; j++){
                    temp.add(dp[i][j]);
                }
                result.add(temp);
            }
            return result;
            
            
            
        }
    }
    

Log in to reply
 

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