Python in place and O(n) extra space solutions. Challenge me :)


  • 0
    R

    DP in place solution, bottom up direction, updates nodes by adding minimum of two underlying nodes

    class Solution:
        # @param triangle, a list of lists of integers
        # @return an integer
        def minimumTotal(self, triangle):
            for level in range(1, len(triangle))[::-1]:
                for i in range(0, len(triangle[level]) - 1):
                    triangle[level-1][i] += min(triangle[level][i], triangle[level][i+1])
            
            return triangle[0][0]
    

    DP with O(n) extra space, if no changes in original triangle allowed, the same idea, using temporary array to store calculated minimal sums

    class Solution:
        # @param triangle, a list of lists of integers
        # @return an integer
        def minimumTotal(self, triangle):
            tmp = triangle[len(triangle) - 1]
            for level in range(1, len(triangle))[::-1]:
                for i in range(0, len(triangle[level]) - 1):
                    tmp [i] = triangle[level-1][i] + min(tmp[i], tmp[i+1])
    
            return tmp[0]

Log in to reply
 

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