120 - Triangle

Difficulty: Medium | Pattern: Dynamic Programming (Bottom-Up) | Company tags: Amazon, Apple, Bloomberg

Problem Statement

Given a triangle array, return the minimum path sum from top to bottom.

For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.

Example:

Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: 2 + 3 + 5 + 1 = 11
    2
   3 4
  6 5 7
 4 1 8 3

Bonus: Use O(n) extra space where n is the number of rows.

Approach: Bottom-Up DP — O(n²) time, O(n) space

Key insight: Start from the bottom row and work upwards. For each cell, the minimum path from that cell to the bottom is triangle[i][j] + min(dp[j], dp[j+1]) where dp holds the minimum paths from the row below.

def minimumTotal(triangle: list[list[int]]) -> int:
    n = len(triangle)
    dp = triangle[-1][:]  # start with a copy of the bottom row
    
    for i in range(n-2, -1, -1):  # work upwards
        for j in range(len(triangle[i])):
            dp[j] = triangle[i][j] + min(dp[j], dp[j+1])
    
    return dp[0]

Dry Run

triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]

Initial dp (bottom row): [4,1,8,3]

Row (i)	Row values	Update dp
i=2	[6,5,7]	dp[0]=6+min(4,1)=7, dp[1]=5+min(1,8)=6, dp[2]=7+min(8,3)=10 → dp=[7,6,10,3]
i=1	[3,4]	dp[0]=3+min(7,6)=9, dp[1]=4+min(6,10)=10 → dp=[9,10,10,3]
i=0	[2]	dp[0]=2+min(9,10)=11 → dp=[11,10,10,3]

Return dp[0] = 11 ✓

Top-Down DP (Alternative)

def minimumTotal(triangle: list[list[int]]) -> int:
    n = len(triangle)
    memo = {}
    
    def dp(row, col):
        if row == n:
            return 0
        if (row, col) in memo:
            return memo[(row, col)]
        result = triangle[row][col] + min(dp(row+1, col), dp(row+1, col+1))
        memo[(row, col)] = result
        return result
    
    return dp(0, 0)

Edge Cases

• Single element [[x]] → return x
• All negative numbers → still works (min picks the least negative)
• All same numbers → any path gives same result

Complexity

Approach	Time	Space
Bottom-up DP	O(n²)	O(n) — single dp array
Top-down with memo	O(n²)	O(n²) — memo table

The bottom-up approach is preferred because it achieves the bonus O(n) space by reusing a single array, working from the last row upward.