algoadvance

Given a triangle array, return the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

Example:

Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11.

Constraints:

Clarifying Questions

  1. Q: Can the triangle array have only negative numbers? A: Yes, the elements can be negative as per the constraints.

  2. Q: Do we need to consider only non-diagonal paths? A: No, each step can move to an adjacent number on the row below.

Strategy

We can solve this problem using dynamic programming. We’ll modify the given triangle in place to store the minimum path sums that lead to each element. We start from the second last row and move upwards, updating the minimum path sum for each element by considering the minimum path sum from the elements directly below it.

Here are the steps to solve the problem:

  1. Start from the second last row of the triangle.
  2. For each element in this row, add the minimum of the two adjacent elements in the row directly below to this element.
  3. Move one row up and repeat the process.
  4. Continue until you have processed the top element of the triangle.
  5. The top element of the triangle will hold the minimum path sum from top to bottom.

Code

Here is the implementation in Python:

def minimumTotal(triangle):
    # Start from the second last row
    for row in range(len(triangle) - 2, -1, -1):
        for col in range(len(triangle[row])):
            # Update the current element 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]

Time Complexity

The time complexity of this solution is O(n^2), where n is the number of rows in the triangle. This is because every element in the triangle is processed a constant number of times (each element is updated once).

The space complexity is O(1) extra space since we are modifying the triangle in place and not using any additional data structures.

This approach ensures that the problem is solved efficiently both in terms of time and space.

Try our interview co-pilot at AlgoAdvance.com