Code Implementation

class Solution:
    def minimumTotal(self, triangle):
        if not triangle:
            return 0
        # Start from the second last row and move upwards
        for row in range(len(triangle) - 2, -1, -1):
            for col in range(len(triangle[row])):
                # Update the current value to be the sum of itself and the min of the two below
                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]
      

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        if (n == 0) return 0;
        // Start from the second last row and move upwards
        for (int row = n - 2; row >= 0; --row) {
            for (int col = 0; col < triangle[row].size(); ++col) {
                triangle[row][col] += min(triangle[row + 1][col], triangle[row + 1][col + 1]);
            }
        }
        return triangle[0][0];
    }
};
      

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        if (n == 0) return 0;
        // Start from the second last row and move upwards
        for (int row = n - 2; row >= 0; row--) {
            for (int col = 0; col < triangle.get(row).size(); col++) {
                int val = triangle.get(row).get(col) +
                    Math.min(triangle.get(row + 1).get(col), triangle.get(row + 1).get(col + 1));
                triangle.get(row).set(col, val);
            }
        }
        return triangle.get(0).get(0);
    }
}
      

var minimumTotal = function(triangle) {
    if (triangle.length === 0) return 0;
    // Start from the second last row and move upwards
    for (let row = triangle.length - 2; row >= 0; row--) {
        for (let col = 0; col < triangle[row].length; col++) {
            triangle[row][col] += Math.min(triangle[row + 1][col], triangle[row + 1][col + 1]);
        }
    }
    return triangle[0][0];
};
      

Problem Description

You are given a triangle array triangle where triangle[i] represents the elements on the ith row of the triangle. Each step, you may move to an adjacent number on the row below (i.e., from element triangle[i][j], you can move to either triangle[i+1][j] or triangle[i+1][j+1]).

Your task is to find the minimum path sum from the top to the bottom of the triangle. You must start at the top element and move only to adjacent numbers on the row below, until you reach the last row. The triangle is guaranteed to have at least one row, and all elements are integers.

• Each move can go to only one of two adjacent numbers in the next row.
• You must not skip rows or move diagonally more than one column at a time.
• Return the minimum possible sum of such a path.

Thought Process

At first glance, the problem seems to require checking every possible path from the top to the bottom of the triangle and finding the one with the smallest sum. This is a classic example of a problem that can be approached with recursion or brute-force, but such methods quickly become inefficient as the triangle grows larger, due to the exponential number of possible paths.

To optimize, we can notice that the minimum path to reach a cell in the triangle depends on the minimum paths to reach the cells above it. This overlapping subproblem structure suggests that dynamic programming is a good fit.

Instead of recalculating the minimum path for each cell repeatedly, we can store and reuse results for subproblems we've already solved. By working from the bottom of the triangle upwards, we can iteratively calculate the minimum path sum for each cell, eventually reaching the top with the answer.

Solution Approach

• Bottom-Up Dynamic Programming: Start from the second-last row of the triangle and move upwards. For each cell, update its value to be the sum of itself and the minimum of its two children (the two adjacent numbers directly below it).
• This way, each cell in the triangle will represent the minimum path sum from that cell to the bottom.
• By the time we reach the top of the triangle, the top cell contains the minimum path sum from top to bottom.
• Why this works: At each step, we only need to make a local decision: for a given cell, we choose the minimum of the two possible paths (left child and right child) and add the current value.
• This approach modifies the triangle in place, so we do not need extra space (besides a few variables), making it space efficient.
• Alternatively, if modifying the triangle is not allowed, we could use a separate array to store the results.

Step-by-step:

1. Start from the second-last row (since the last row is the base case).
2. For each cell in the current row, update it to be its value plus the minimum of the two values directly below it.
3. Repeat this process for each row moving upwards.
4. After processing the top row, the top element contains the minimum path sum.

Example Walkthrough

Consider the triangle:
[
  [2],
  [3,4],
  [6,5,7],
  [4,1,8,3]
]

1. Start at the second last row: [6,5,7]
   • For 6: min(4,1) = 1, so 6+1=7
   • For 5: min(1,8) = 1, so 5+1=6
   • For 7: min(8,3) = 3, so 7+3=10
   • Now row is [7,6,10]
2. Move up to row [3,4]:
   • For 3: min(7,6) = 6, so 3+6=9
   • For 4: min(6,10) = 6, so 4+6=10
   • Now row is [9,10]
3. Move up to top row [2]:
   • For 2: min(9,10) = 9, so 2+9=11
   • Now row is [11]
4. Result: The minimum path sum is 11.

Time and Space Complexity

• Brute-force Approach:
  • Would involve exploring every possible path from top to bottom.
  • There are 2^n-1 possible paths for a triangle with n rows.
  • Time complexity: O(2ⁿ), which is exponential and infeasible for large n.
  • Space complexity: O(n) for recursion stack.
• Optimized Dynamic Programming Approach:
  • Each cell is visited exactly once.
  • For a triangle with n rows, there are (n(n+1))/2 elements.
  • Time complexity: O(n²), since we process each element once.
  • Space complexity: O(1) if we modify the triangle in place, or O(n) if we use an extra array for the current row.

Summary

The Triangle problem is a classic dynamic programming challenge that demonstrates how recognizing overlapping subproblems and optimal substructure can lead to efficient solutions. By starting from the bottom and working upwards, we avoid redundant calculations and achieve a time and space-efficient algorithm. The key insight is to reuse results for subproblems, updating each cell with the minimum sum path to the bottom, and ending with the answer at the top of the triangle.