18-line C++ DP Solution, O(n), Easy to Understand


  • 8

    Simple DP, just check if the neigbours know how far are they to the nearest 0 when I don't know

    class Solution {
    public:
        vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
            int h=matrix.size(), w=matrix[0].size();
            vector<vector<int>> dp(h,vector<int>(w,INT_MAX));
            for(int times=0;times<=1;times++) // two passes, first forward then backward
                for(int i=times?h-1:0;times?i>=0:i<h;times?i--:i++) 
                    for(int j=times?w-1:0;times?j>=0:j<w;times?j--:j++)
                            if(matrix[i][j]==0)
                                dp[i][j]=0;
                            else {
                                if(i&&dp[i-1][j]!=INT_MAX&&dp[i][j]>dp[i-1][j]+1) // look up
                                    dp[i][j]=dp[i-1][j]+1;
                                if(j&&dp[i][j-1]!=INT_MAX&&dp[i][j]>dp[i][j-1]+1) // look left
                                    dp[i][j]=dp[i][j-1]+1;
                                if(i<h-1&&dp[i+1][j]!=INT_MAX&&dp[i][j]>dp[i+1][j]+1) // look down
                                    dp[i][j]=dp[i+1][j]+1;
                                if(j<w-1&&dp[i][j+1]!=INT_MAX&&dp[i][j]>dp[i][j+1]+1) // look right
                                    dp[i][j]=dp[i][j+1]+1;
                            }
            return dp;
        }
    };
    

  • 0
    D

    a great idea!
    thanks a lot for the different solution!


  • 0
    Y
    This post is deleted!

  • 1
    N

    Not sure if it is really a DP, but based on the same idea, and directly use matrix as dp table. Here is my Python version.

    It takes 675 ms to run. It is faster than my BFS version https://discuss.leetcode.com/topic/83571/python-bfs, which takes 986 ms.

    class Solution(object):
        def check(self, matrix, height, width, i, j):
            if (i > 0 and matrix[i-1][j] + 1 < matrix[i][j]):
                matrix[i][j] = matrix[i-1][j] + 1
            if (i + 1 < height and matrix[i+1][j] + 1 < matrix[i][j]):
                matrix[i][j] = matrix[i+1][j] + 1
            if (j > 0 and matrix[i][j-1] + 1 < matrix[i][j]):
                matrix[i][j] = matrix[i][j-1] + 1
            if (j + 1 < width and matrix[i][j+1] + 1 < matrix[i][j]):
                matrix[i][j] = matrix[i][j+1] + 1
            
        def updateMatrix(self, matrix):
            """
            :type matrix: List[List[int]]
            :rtype: List[List[int]]
            """
            height = len(matrix)
            width = len(matrix[0])
            for i in xrange(height):
                for j in xrange(width):
                    if matrix[i][j] != 0:
                        matrix[i][j] = height + width
                        
            # traverse forward
            for i in xrange(height):
                for j in xrange(width):
                    if matrix[i][j] == 0:
                        continue
                    self.check(matrix, height, width, i, j)
                    
            # traverse backward
            for i in xrange(height - 1, -1, -1):
                for j in xrange(width -1, -1, -1):
                    if matrix[i][j] == 0:
                        continue
                    self.check(matrix, height, width, i, j)
            
            return matrix
    

  • 1
    L

    Nice solution.
    One backward and one forward to make sure the nearest 0.


  • 0
    C

    Indeed nice.
    I had thought only what is below AND right of a zero gets set forwards, and only what is above AND to the left of a zero going backwards. But because we propagate across the whole row, the first pass gets anything below anything to the right of a zero. Then on the way backwards, the bottom row gets completed, and that propagates up.


  • 2
    Y

    code style is a problem.


  • 0

    @yuanqili This is called Line-Crushing style.


  • 1
    J

    It still confuses me that why exactly 2 passes are needed. Could anybody give any theoretical proof about it?


  • 7
    Y

    @jtimberlakers
    The first pass makes sure we have distance to nearest zero from top-left direction.
    The second pass makes sure we have distance to nearest zero from bottom-right direction.

    It is more clear it write this way (Java):

    public int[][] updateMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] ans = new int[m][n];
        for (int[] row : ans)       
            Arrays.fill(row, m + n);                
    
        // top-left to bottom-right         
        for (int r = 0; r < m; r++) {       
            for (int c = 0; c < n; c++) {                   
                if (matrix[r][c] == 0) ans[r][c] = 0;                                              
                else {
                    if (r > 0) ans[r][c] = Math.min(ans[r][c], 1 + ans[r - 1][c]);
                    if (c > 0) ans[r][c] = Math.min(ans[r][c], 1 + ans[r][c - 1]);
                }
            }                           
        }
                                                                    
        // bottom-right to top-left
        for (int r = m - 1; r >= 0; r--) {                                          
            for (int c = n - 1; c >= 0; c--) {              
                if (matrix[r][c] == 0) ans[r][c] = 0;
                else {
                    if (r < m - 1) ans[r][c] = Math.min(ans[r][c], 1 + ans[r + 1][c]); 
                    if (c < n - 1) ans[r][c] = Math.min(ans[r][c], 1 + ans[r][c + 1]);
                }                                                   
            }
        }                                           
                                                    
        return ans;
    }
    

  • 0
    E

    Thank you for your solution.

    Here's a little suggestion. Because INT_MAX++ will lead to a overflow, the if statement does a judgement.
    However, if the dp matrix is initialized with INT_MAX - 1(or which is a bit larger than 2 times of matrix's size), there's no need to judge dp[i-1][j] != INT_MAX in the if-condition.


  • 0
    Y

    @luming89 Nice idea. Obviously, you don't like using space.


  • 0
    B

    @yuxiangmusic why filling the array with row+col work not any other.


  • 0
    C

    Some thoughts on why two passes are enough to find the shortest path. Suppose there is a directed path p from a 0 to an e(i, j) in the matrix and suppose this path is shortest, so that dp[i, j] = length(p) after the code terminates. The top-down & left-right pass will optimize any subpath of p that has directions down or right, the bottom-up & right-left pass will optimize any subpath of p that has direction up or left.


Log in to reply
 

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