We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Triangle

Number: 120

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Goldman Sachs, Oracle, Bloomberg, Walmart Labs, Apple, Agoda, Microsoft, Salesforce, DE Shaw

Problem Description

Given a triangle array, return the minimum path sum from top to bottom. At each step, you may move to an adjacent number on the row below. For example, if you are on index i on the current row, you can move to index i or i + 1 on the next row.

Key Insights

  • Use dynamic programming to reduce overlapping subproblems.
  • A bottom-up approach is most efficient by calculating the minimum path sums from the bottom row upward.
  • This method reduces extra space usage to O(n) where n is the number of rows.
  • The solution iteratively updates a dp array that eventually holds the minimum path sum at its first index.

Space and Time Complexity

Time Complexity: O(n^2) where n is the number of rows (each element is processed once). Space Complexity: O(n) extra space is used for the dp array storing one row of results.

Solution

A bottom-up dynamic programming approach is used to handle this problem. First, initialize a dp array as a copy of the last row of the triangle. Then, starting from the second-to-last row, update each element in the dp array by adding the current triangle element to the minimum of the two adjacent numbers from the row below (already stored in dp). By the time you reach the top row, dp[0] holds the minimum total path sum. The dp array is updated in place to ensure an O(n) space solution.

Code Solutions

def minimumTotal(triangle):
    # If the triangle is empty, return 0
    if not triangle:
        return 0
    # Start with a copy of the last row which acts as our dp array
    dp = triangle[-1][:]
    # Process the triangle from the second last row up to the top row
    for row in range(len(triangle) - 2, -1, -1):
        for col in range(len(triangle[row])):
            # Update dp array by adding the current triangle element
            # to the minimum of its two children in the dp array
            dp[col] = triangle[row][col] + min(dp[col], dp[col + 1])
    return dp[0]

# Example usage:
triangle1 = [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]
print(minimumTotal(triangle1))  # Output: 11
← Back to All Questions