Minimum Path Sum in Triangular Structure : Coding problem #1

You’re given a triangular structure represented as an array of arrays, where each sub-array represents a row of numbers. Your task is to find the path from the top to the bottom of the triangle with the minimum sum.

At each step, you’re allowed to move to an adjacent number in the row below. Adjacent here means moving either directly below the current position or one step to the right.

For instance, given the triangular structure:

   2
  3 4
 6 5 7
4 1 8 3

The minimum path sum from top to bottom would be 2 + 3 + 5 + 1 = 11.

Constraints to consider are:

• The number of rows in the triangle is at least 1 and at most 200.
• The number of elements in the first row is always 1.
• Each subsequent row has one more element than the previous row.
• The values of the elements in the triangle range from -10,000 to 10,000.

Solution:

Approach 1 using python

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        # Get the number of rows in the triangle
        n = len(triangle)

        # Start from the second row and iteratively update the triangle
        for i in range(1, n):
            for j in range(len(triangle[i])):
                # If it's the first element in the row, consider only the element above
                if j == 0:
                    triangle[i][j] += triangle[i - 1][j]
                # If it's the last element in the row, consider only the element above and to the left
                elif j == len(triangle[i]) - 1:
                    triangle[i][j] += triangle[i - 1][j - 1]
                # For other elements, choose the minimum of the two adjacent elements above
                else:
                    triangle[i][j] += min(triangle[i - 1][j - 1], triangle[i - 1][j])

        # The minimum path sum will be the minimum value in the last row
        return min(triangle[-1])
  

The code iterates through a triangle of numbers, starting from the second row, and updates each number to be the minimum sum of the path from the top to that number. It does this by adding the current number to the minimum of the two numbers directly above it in the previous row. Finally, it returns the minimum number in the last row, representing the minimum path sum from the top to the bottom of the triangle.

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 we’re iterating over each element in the triangle once.

Space Complexity: The space complexity is O(1), as we only use a small amount of extra memory to store the updated triangle. The input triangle is modified in place.