Triangle

Intuition

We could update the triangle in down-top order. For each number, we would update it to the minimum path sum from it to bottom.

By modifying it in place, this could be solved with O(1) extra space.

Solution


class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        if not triangle:
            return 0

        for row in range(len(triangle) - 2, -1, -1):
            for i in range(row + 1):
                triangle[row][i] += min(triangle[row + 1][i], triangle[row + 1][i + 1])
        return triangle[0][0]