120.Triangle(Medium).md

120. Triangle (Medium)

Date and Time: Oct 12, 2024, 16:06 (EST)

Link: https://leetcode.com/problems/triangle/

Question:

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 1:

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

Output: 11

Explanation:

The triangle looks like:
   2
  3 4
 6 5 7
4 1 8 3
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).

Example 2:

Input: triangle = [[-10]]

Output: -10

Constraints:

• 1 <= triangle.length <= 200

• triangle[0].length == 1

• triangle[i].length == triangle[i - 1].length + 1

• -10^4 <= triangle[i][j] <= 10^4

Walk-through:

1. We start from the bottom-up and find the recurrence relation that dp[r][c] += min(dp[r+1][c], dp[r+1][c+1]).

2. Finally, we wanna return the top of dp.

To save the Space Complexity, we find that we only need to use the previous row of dp to find the minimum of the previous dp row. And we can update the dp.

Python Solution:

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        # DP: bottom-up
        # Recurrence Relation: dp[r][c] += min(dp[r+1][c], dp[r+1][c+1])
        # return dp[0][0]
        
        # TC: O(n^2), SC: O(n^2)
        dp = triangle
        for row in range(len(triangle)-2, -1, -1):
            for col in range(len(triangle[row])):
                dp[row][col] += min(dp[row+1][col], dp[row+1][col+1])
                
        return dp[0][0]

Time Complexity: $O(n^2)$, n is the length of triangle.
Space Complexity: $O(n^2)$

Python Optimized Space Complexity:

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        # use a dp[] to keep track of previous path sum, bottom-up
        # update new dp with current col's val + min(dp[col], dp[col+1])
        # return the first element of dp in the end

        # TC: O(n^2), SC: O(1)
        dp = [0] * (len(triangle) + 1)  # Base case
        for row in triangle[::-1]:
            for i, col in enumerate(row):
                dp[i] = col + min(dp[i], dp[i+1])
        
        return dp[0]

Time Complexity: $O(n^2)$
Space Complexity: $O(n)$