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.

Approach 2 using python

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        memo = {}

        def find_minimum_path(triangle, row, col):
            if row == len(triangle):
                return 0

            if (row, col) in memo:
                return memo[(row, col)]

            current_value = triangle[row][col]
            min_path_sum = current_value + min(find_minimum_path(triangle, row+1, col), find_minimum_path(triangle, row+1, col+1))
            memo[(row, col)] = min_path_sum

            return min_path_sum

        return find_minimum_path(triangle, 0, 0)

The code uses a technique called memoization to avoid recomputing subproblems. The memo dictionary stores the results of subproblems, and the function checks if a subproblem has already been solved before recomputing it.

The recursive function find_minimum_path explores all possible paths from a given position to the bottom of the triangle, and returns the minimum path sum. The function uses the memo dictionary to store the results of subproblems, which allows it to avoid recomputing them.

The time complexity of this solution is O(n^2), where n is the number of rows in the triangle because each subproblem is solved only once and stored in the memo dictionary. The space complexity is O(n^2) as well, because the memo dictionary stores the results of all subproblems.

Approach 3 using Python

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        n = len(triangle)
        dp = [[0] * len(row) for row in triangle]

        dp[0][0] = triangle[0][0]

        for i in range(1, n):
            dp[i][0] = dp[i-1][0] + triangle[i][0]
            dp[i][-1] = dp[i-1][-1] + triangle[i][-1]
            for j in range(1, len(triangle[i])-1):
                dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]

        return min(dp[-1])

This code is a dynamic programming solution to the “Triangle” problem, where you need to find the minimum path sum from the top to the bottom of a triangle.

Here’s a step-by-step breakdown of how the code works:

Initialization

• n = len(triangle): Get the number of rows in the triangle.
• dp = [[0] * len(row) for row in triangle]: Create a 2D list dp with the same shape as the triangle, filled with zeros. This will store the minimum path sums for each position in the triangle.

Base case

• dp[0][0] = triangle[0][0]: Set the top element of dp to the top element of the triangle. This is the starting point of the path.

Dynamic programming

The code then iterates over each row of the triangle, starting from the second row (index 1).

For each row i:

• dp[i][0] = dp[i-1][0] + triangle[i][0]: Set the first element of the current row to the sum of the first element of the previous row and the current element. This is because the only path to the first element of the current row is from the first element of the previous row.
• dp[i][-1] = dp[i-1][-1] + triangle[i][-1]: Set the last element of the current row to the sum of the last element of the previous row and the current element. This is because the only path to the last element of the current row is from the last element of the previous row.
• For each element j in the middle of the current row (index 1 to len(triangle[i])-2):
  • dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]: Set the current element to the minimum sum of the two adjacent elements above (left and right) and the current element. This is because the path to the current element can come from either the left or right adjacent element above.

Final result

• return min(dp[-1]): Return the minimum path sum, which is the minimum value in the last row of dp.

The key insight here is that the minimum path sum to each element in the triangle depends only on the minimum path sums of the adjacent elements above. By iteratively updating the dp table, we can compute the minimum path sum for each element in the triangle, and finally return the minimum value in the last row.

Don't Miss Out! Subscribe to Read Our Latest Blogs.

If you found this blog helpful, share it on social media.