Triangle

Naive Approach: Brute Force

The most straightforward approach is to explore all possible paths from the top to the bottom of the triangle and compute the sum of each path. Then, we can return the minimum of these sums.

Algorithm:

1. Start at the top of the triangle (triangle[0][0]).
2. Recursively explore each possible path by moving to an adjacent number in the row below (either the same index or the next index).
3. Keep track of the sum of each path.
4. Return the minimum sum among all paths.

Code:

def min_path_sum_recursive(triangle, row, col):
    if row == len(triangle) - 1:
        return triangle[row][col]
    
    return triangle[row][col] + min(
        min_path_sum_recursive(triangle, row + 1, col),
        min_path_sum_recursive(triangle, row + 1, col + 1)
    )

def minimumTotal_brute_force(triangle):
    return min_path_sum_recursive(triangle, 0, 0)

Time Complexity:

O(2^n), where n is the number of rows in the triangle. Each element has two possible paths to take, resulting in exponential time complexity.

Space Complexity:

O(n), where n is the number of rows, due to the recursive call stack.

Optimal Approach: Dynamic Programming

Dynamic programming can significantly optimize the solution by avoiding redundant calculations. We can use a bottom-up approach.

Algorithm:

1. Create a DP table (or modify the original triangle) to store the minimum path sum to reach each element.
2. Start from the bottom row and move upwards.
3. For each element, the minimum path sum is the element's value plus the minimum of the two adjacent elements in the row below.
4. The top element of the DP table will contain the minimum path sum from top to bottom.

Code:

def minimumTotal_dp(triangle):
    n = len(triangle)
    dp = triangle[-1][:]  # Initialize DP table with the last row

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

    return dp[0]

Time Complexity:

O(n^2), where n is the number of rows in the triangle. We iterate through each element of the triangle once.

Space Complexity:

O(n), where n is the number of rows, because the dp array stores the minimum sums for the current row being processed.

Space Complexity Optimization (In-Place):

The algorithm can be further optimized to use O(1) extra space (excluding the space used by the input triangle) by modifying the original triangle in place.

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

Edge Cases:

• Empty Triangle: If the triangle is empty (triangle = []), return 0 or handle it as an error, based on the problem's requirements.
• Single Row Triangle: If the triangle has only one row (triangle = [[value]]), return that value.
• Null or Invalid Input: Check for null or invalid input to prevent runtime errors.