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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Triangle

Difficulty: Medium

Problem Description

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.

Key Insights

  • The problem can be solved using dynamic programming by calculating the minimum path sum at each position in the triangle.
  • We can start from the second-to-last row and work our way up to the top of the triangle, updating the current row with the minimum path sums.
  • This approach allows us to use only O(n) extra space by modifying the triangle in place.

Space and Time Complexity

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

Solution

The solution utilizes a bottom-up dynamic programming approach. Starting from the second-to-last row of the triangle, we iteratively update each element to represent the minimum path sum from that element to the bottom of the triangle. The key data structure used here is the triangle array itself, which is modified to store the minimum sums.

Code Solutions

def minimumTotal(triangle):
    # Start from the second to last row and move upwards
    for row in range(len(triangle) - 2, -1, -1):
        for col in range(len(triangle[row])):
            # Update the current cell with the minimum path sum
            triangle[row][col] += min(triangle[row + 1][col], triangle[row + 1][col + 1])
    # The top element now contains the minimum path sum
    return triangle[0][0]
← Back to All Questions