Why is my linear python DFS solution get runtime error?


  • 0
    B

    My solution starts from the first 0 and recurses on the neighbors. I also keep track of the locations visited.

    The recursion stops when if a location is visited and current distance to zero is less than existing distance to zero. The dfs should be O(4n) since each spot will be visited at most 4 times.

    It fails on a large matrix. Not sure why.

    def updateMatrix(self, matrix):
        visited = [[False] * len(matrix[0]) for _ in matrix]
        def helper(r, c, matrix, distToZero):
            if r >= len(matrix) or c >= len(matrix[0]) or min(r, c) < 0:
                return
            if visited[r][c] and matrix[r][c] <= distToZero:
                return
            visited[r][c] = True
            if matrix[r][c] == 0:
                distToZero = 0
            matrix[r][c] = distToZero
            helper(r + 1, c, matrix, distToZero + 1)
            helper(r - 1, c, matrix, distToZero + 1)
            helper(r, c + 1, matrix, distToZero + 1)
            helper(r, c - 1, matrix, distToZero + 1)
        
    
        for r in range(0, len(matrix)):
            for c in range(0, len(matrix[0])):
                if matrix[r][c] == 0:
                    helper(r, c, matrix, 0)
                    return matrix
        return None
    

Log in to reply
 

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