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

• 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]``````

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