Python O(1)space O(n) time from bottom up Solution 94%beat


  • 0
    T
    class Solution(object):
        def minimumTotal(self, triangle):
            """
            :type triangle: List[List[int]]
            :rtype: int
            """
            n = len(triangle)
            if n == 0:
                return 0
            i = n-2
            while i >= 0:
                m = len(triangle[i])
                for j in xrange(m):
                    triangle[i][j] = min(triangle[i + 1][j], triangle[i + 1][j + 1]) + triangle[i][j]
                i -= 1
            return triangle[0][0]
    

Log in to reply
 

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