Triangle Leetcode Problem 120 [Python Solution]

In this blog post, we will tackle the Triangle LeetCode problem, specifically Problem 120 and provide a Python solution to find the minimum path sum from the top to the bottom of a given triangle array.

Before we dive into the solution, let’s start with an overview of the problem.

Problem Overview

Problem Statement

Given a triangle array, you need to find the minimum path sum from top to bottom.

Each step allows you to move to an adjacent number of the row below.

More formally, if you are at index i on the current row, you can move to either index i or i + 1 on the next row.

Example

Let’s consider an example to illustrate the problem.

Given the following triangle:

   2
  3 4
 6 5 7
4 1 8 3

The minimum path sum from the top to the bottom is 2 + 3 + 5 + 1, which equals 11.

Constraints

The problem comes with the following constraints:

• The number of rows in the triangle array is in the range [1, 200].
• The length of the first row of the triangle is 1.
• For rows other than the first, the length is one more than the length of the previous row.
• The values within the triangle range from -10^4 to 10^4. Now, let’s explore how to approach this problem efficiently and provide a Python solution.

Efficient Python Code Solution

def minimumTotal(triangle):
    dp = triangle[-1]  # Initialize dp with the last row of the triangle

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

    return dp[0]

Time and Space Complexity

Time Complexity

The time complexity of this solution is O(n^2), where n is the number of rows in the triangle.

We iterate through the triangle twice, once from bottom to top and once from left to right, with each iteration having a complexity of O(n).

Space Complexity

The space complexity is O(n) since we only need to maintain one row of the triangle for dynamic programming, and the size of this row is determined by the number of rows in the triangle.

Reasoning Behind Our Approach

The key insight to solving this problem efficiently is to work from the bottom of the triangle upwards.

By starting at the last row, we can compute the minimum path sum for each element by considering the two possible paths it can take to reach the bottom.

We keep track of these sums in a dynamic programming array dp, which is initialized with the last row of the triangle.

As we move up the triangle, we update the dp array with the minimum path sums.

Related Interview Questions By Company:

• Unique Paths II LeetCode
• Find First And Last Position Of Element In Sorted Array LeetCode
• Merge Triplets To Form Target Triplet LeetCode

Related Interview Questions By Difficulty:

• Combination Sum Iv LeetCode
• Triangle LeetCode
• Min Cost Climbing Stairs LeetCode

Related Interview Questions By Category:

• Verifying An Alien Dictionary LeetCode
• Last Stone Weight II LeetCode
• Seat Reservation Manager LeetCode

Conclusion

In this blog post, we addressed the Triangle LeetCode problem (Problem 120) and provided an efficient Python solution that calculates the minimum path sum from the top to the bottom of a given triangle array.

We also discussed the time and space complexity of our solution.

We hope this explanation and solution have been helpful for your understanding of this problem.

If you have any questions, suggestions, or want to explore more problems, please feel free to comment and engage with us.

You can find the original problem description and more details on the LeetCode website.

Happy coding!