Linear AC solution, 2 pass.


  • 0
    X
    def updateMatrix(self, matrix):
            for i in range(len(matrix)):
                for j in range(len(matrix[i])):
                    if matrix[i][j] == 1:
                        matrix[i][j] = float('inf')
                        if i > 0:
                            matrix[i][j] = min(matrix[i][j], matrix[i-1][j]+1)
                        if j > 0:
                            matrix[i][j] = min(matrix[i][j], matrix[i][j-1]+1)
            for i in reversed(range(len(matrix))):
                for j in reversed(range(len(matrix[0]))):
                    if matrix[i][j] > 0:
                        if i < len(matrix)-1:
                            matrix[i][j] = min(matrix[i][j], matrix[i+1][j]+1)
                        if j < len(matrix[0])-1:
                            matrix[i][j] = min(matrix[i][j], matrix[i][j+1]+1)
            return matrix
    

Log in to reply
 

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