Python DP solution O(n)


  • 1
    K

    For this question, we only need to consider 4 direction, up, down ,left and right.
    so, first, I go through this matrix from top-left to down-right, and we can find the minimum distance from up and left, then, go through the matrix from down-right to top-left, so we can find the minimum distance from down and right. and it said the elements will not exceed 10,000, so I just set the initial value as 10,000.

        def updateMatrix(self, matrix):
            """
            :type matrix: List[List[int]]
            :rtype: List[List[int]]
            """
            dic = {}
            if not matrix or not matrix[0]:
                return matrix
            h,w = len(matrix),len(matrix[0])
            mask = [[10000]*w for i in xrange (h)]
            for i in xrange (h):
                for j in xrange (w):
                    if matrix[i][j] != 0:
                        mask[i][j] = min(mask[i][j],mask[i-1][j]+1,mask[i][j-1]+1)
                    else:
                        mask[i][j] = 0
            for i in xrange (h-1,-1,-1):
                for j in xrange (w-1,-1,-1):
                    if matrix[i][j] != 0:
                        if i < h-1:
                            mask[i][j] = min(mask[i][j],mask[i+1][j] + 1)
                        if j < w-1:
                            mask[i][j] = min(mask[i][j],mask[i][j+1] + 1)
            return mask
    

    If you have any better idea, please let me know! Thanks!


  • 0
    R

    can you explain a bit how you got to the conclusion of iterating twice through the matrix?


  • 0
    K

    @robinenrique
    For the first time of iteration, we go through the matrix from top to down , left to right:
    mask[i][j] will record the minimum distance from i,j to the nearest 0 from up and left.

    For the second time of iteration, we go through the matrix from down to top , right to left:
    mask[i][j] will record the minimum distance from i,j to the nearest 0 from down and right and up and left(which is already store in mask[i][j]) .

    Is it clear?


Log in to reply
 

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