# Triangle
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/triangle)
Canonical: https://scaleengineer.com/dsa/problems/triangle
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
**Companies:** [Agoda](https://scaleengineer.com/companies/agoda), [Salesforce](https://scaleengineer.com/companies/salesforce), [DE Shaw](https://scaleengineer.com/companies/de-shaw)
---
## Problem
Given a `triangle` array, return _the minimum path sum from top to bottom_.

For each step, you may move to an adjacent number of the row below. More formally, if you are on index `i` on the current row, you may move to either index `i` or index `i + 1` on the next row.

**Example 1:**

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

**Example 2:**

**Input:** triangle = [[-10]]
**Output:** -10

**Constraints:**

* `1 <= triangle.length <= 200`
* `triangle[0].length == 1`
* `triangle[i].length == triangle[i - 1].length + 1`
* `-104 <= triangle[i][j] <= 104`

**Follow up:** Could you do this using only `O(n)` extra space, where `n` is the total number of rows in the triangle?

# Approaches
## Brute-Force Recursion
The most intuitive way to solve this problem is to think about it recursively. Starting from the top of the triangle at `(0, 0)`, we have two choices at each step: move to the element at index `j` or `j+1` in the row below. We can explore all possible paths from top to bottom, calculate the sum for each path, and then find the minimum among them. This can be implemented with a simple recursive function.
**Time:** O(2^N) · **Space:** O(N)
**Pros:** Simple to conceptualize and implement.; Directly translates the problem definition into code.
**Cons:** Extremely inefficient due to exponential time complexity.; It recomputes the same subproblems multiple times, leading to a 'Time Limit Exceeded' error on most platforms for non-trivial inputs.
### Explanation
This approach defines a recursive function that explores every possible path from the top to the bottom of the triangle. For each node, it makes two recursive calls for its two children in the next row. The function returns the sum of the current node's value and the minimum of the results from its two children's recursive calls. The base case for the recursion is when a path reaches the last row, at which point it returns the value of the node in that row.

```java
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        return solve(0, 0, triangle);
    }

    private int solve(int row, int col, List<List<Integer>> triangle) {
        // Base case: if we are at the last row, return the element's value.
        if (row == triangle.size() - 1) {
            return triangle.get(row).get(col);
        }

        // Recursive step: calculate sum for paths going down and down-right.
        int pathDown = solve(row + 1, col, triangle);
        int pathDiagonal = solve(row + 1, col + 1, triangle);

        // Return the current element's value plus the minimum of the two paths.
        return triangle.get(row).get(col) + Math.min(pathDown, pathDiagonal);
    }
}
```
### Algorithm
1. Define a recursive function `solve(row, col)` that calculates the minimum path sum starting from `triangle[row][col]`.
2. **Base Case:** If `row` is the last row of the triangle (`row == triangle.size() - 1`), the path sum is just the value of the element itself, so return `triangle[row][col]`.
3. **Recursive Step:** For any other cell `(row, col)`, the path must go to either `(row + 1, col)` or `(row + 1, col + 1)`. Recursively calculate the minimum path sum from these two children nodes:
   - `path1 = solve(row + 1, col)`
   - `path2 = solve(row + 1, col + 1)`
4. The minimum path sum from `(row, col)` is the current element's value plus the minimum of the two sub-paths: `triangle[row][col] + min(path1, path2)`.
5. The final answer is the result of the initial call `solve(0, 0)`.

## Top-Down Dynamic Programming with Memoization
The brute-force recursive approach suffers from re-calculating the minimum path sum for the same nodes multiple times. This is a classic sign of overlapping subproblems, which suggests that dynamic programming can be applied. By storing the results of subproblems in a memoization table (a 2D array), we can avoid redundant computations. This is known as a top-down dynamic programming approach.
**Time:** O(N^2) · **Space:** O(N^2)
**Pros:** Drastically improves time complexity from exponential to polynomial.; Guarantees that each subproblem is solved only once.; Maintains the logical structure of the recursive solution.
**Cons:** Requires O(N^2) extra space for the memoization table, which can be substantial for a large triangle.
### Explanation
We enhance the recursive solution by adding a cache (memoization table), typically a 2D array `memo`, to store the minimum path sum for each cell `(row, col)`. Before making recursive calls, we check if the result for the current cell is already in our cache. If it is, we return the cached value directly. Otherwise, we compute the result, store it in the cache, and then return it. This ensures that the minimum path sum for each cell is computed only once.

```java
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        Integer[][] memo = new Integer[n][n];
        return solve(0, 0, triangle, memo);
    }

    private int solve(int row, int col, List<List<Integer>> triangle, Integer[][] memo) {
        // Base case
        if (row == triangle.size() - 1) {
            return triangle.get(row).get(col);
        }

        // Check if the result is already memoized
        if (memo[row][col] != null) {
            return memo[row][col];
        }

        // Recursive step
        int pathDown = solve(row + 1, col, triangle, memo);
        int pathDiagonal = solve(row + 1, col + 1, triangle, memo);

        // Memoize the result and return
        memo[row][col] = triangle.get(row).get(col) + Math.min(pathDown, pathDiagonal);
        return memo[row][col];
    }
}
```
### Algorithm
1. Create a 2D array, `memo`, of the same dimensions as the triangle to store the results of subproblems. Initialize it with a sentinel value (e.g., `null`).
2. Define a recursive function `solve(row, col, memo)`.
3. **Base Case:** If `row` is the last row, return `triangle[row][col]`.
4. **Memoization Check:** Before computing, check if `memo[row][col]` has already been calculated. If so, return the stored value.
5. **Recursive Step:** If the result is not in the memo table, recursively call the function for the two children nodes:
   - `path1 = solve(row + 1, col, memo)`
   - `path2 = solve(row + 1, col + 1, memo)`
6. **Store and Return:** Calculate the minimum path sum `triangle[row][col] + min(path1, path2)`, store it in `memo[row][col]`, and then return it.

## Bottom-Up Dynamic Programming (Tabulation)
Instead of a top-down recursive approach, we can solve the problem iteratively in a bottom-up fashion. This is known as tabulation. We start from the destination (the bottom row of the triangle) and work our way up to the start (the top of the triangle). The minimum path sum for a cell is its own value plus the minimum of the path sums of the two cells directly below it.
**Time:** O(N^2) · **Space:** O(N^2)
**Pros:** Avoids recursion overhead, which can lead to slightly better performance in practice.; Can be more intuitive for problems where the dependency flow is clear.
**Cons:** Like the memoization approach, it requires O(N^2) extra space.
### Explanation
This approach uses a 2D array, `dp`, to store the minimum path sums. We begin by filling the last row of our `dp` table with the values from the last row of the input triangle, as the minimum path from any of these cells to the bottom is just the cell's value itself. Then, we iterate upwards, from row `N-2` to `0`. For each cell `(i, j)`, we calculate its minimum path sum by adding its value to the minimum of the two already-computed path sums in the row below it (`dp[i+1][j]` and `dp[i+1][j+1]`). The final answer is the value computed for the top cell, `dp[0][0]`.

```java
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        if (n == 0) return 0;
        
        int[][] dp = new int[n][n];

        // Initialize the last row of dp with the last row of the triangle
        for (int j = 0; j < n; j++) {
            dp[n - 1][j] = triangle.get(n - 1).get(j);
        }

        // Iterate from the second to last row up to the top
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                // Calculate the minimum path sum for the current cell
                dp[i][j] = triangle.get(i).get(j) + Math.min(dp[i + 1][j], dp[i + 1][j + 1]);
            }
        }

        // The result is at the top of the triangle
        return dp[0][0];
    }
}
```
### Algorithm
1. Create a 2D DP table, `dp`, of size `N x N`, where `N` is the number of rows.
2. **Initialization:** Copy the last row of the `triangle` into the last row of the `dp` table. This is our base case.
   - `dp[N-1][j] = triangle[N-1][j]` for `j` from `0` to `N-1`.
3. **Iteration:** Iterate from the second-to-last row (`i = N-2`) up to the first row (`i = 0`).
4. For each row `i`, iterate through its elements from `j = 0` to `j = i`.
5. **DP Transition:** Calculate the value for `dp[i][j]` using the values from the row below, which have already been computed:
   - `dp[i][j] = triangle[i][j] + min(dp[i+1][j], dp[i+1][j+1])`
6. **Result:** After the loops complete, the minimum total path sum will be stored in `dp[0][0]`.

## Space-Optimized Bottom-Up Dynamic Programming
Observing the bottom-up DP approach, we can see that to compute the minimum path sums for a row `i`, we only need the results from the row immediately below it, `i+1`. We don't need any information from rows `i+2`, `i+3`, etc. This allows us to optimize the space complexity from O(N^2) to O(N) by using a single 1D array to store the results of the previously processed row.
**Time:** O(N^2) · **Space:** O(N)
**Pros:** Highly space-efficient, meeting the follow-up requirement of O(N) extra space.; Maintains the efficient O(N^2) time complexity.
**Cons:** The in-place update of the 1D array can be slightly less intuitive to grasp initially compared to the 2D DP table.
### Explanation
This approach follows the same bottom-up logic but uses only a 1D array, `dp`, of size `N` (the number of rows). We first initialize this `dp` array with the values from the last row of the triangle. Then, we iterate from the second-to-last row up to the top. In the inner loop for each row `i`, we update `dp[j]` by calculating `triangle[i][j] + min(dp[j], dp[j+1])`. Here, `dp[j]` and `dp[j+1]` still hold the values from the row `i+1`. By the time we finish iterating through row `i`, the `dp` array contains the minimum path sums starting from row `i`. This process continues until we reach the top, and the final answer is `dp[0]`.

```java
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[] dp = new int[n];

        // Initialize dp with the last row of the triangle
        for (int j = 0; j < n; j++) {
            dp[j] = triangle.get(n - 1).get(j);
        }

        // Iterate from the second to last row up to the top
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                // Update dp[j] in place. It represents the minimum path sum
                // starting from triangle[i][j].
                dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j+1]);
            }
        }

        // The final result is at dp[0]
        return dp[0];
    }
}
```
### Algorithm
1. Create a 1D array, `dp`, of size `N`, where `N` is the number of rows.
2. **Initialization:** Initialize `dp` with the values from the last row of the `triangle`.
   - `dp[j] = triangle[N-1][j]` for `j` from `0` to `N-1`.
3. **Iteration:** Iterate from the second-to-last row (`i = N-2`) up to the first row (`i = 0`).
4. For each row `i`, iterate through its elements from `j = 0` to `j = i`.
5. **DP Transition:** Update the `dp` array in place. The new `dp[j]` will be the minimum path sum starting from `triangle[i][j]`. This is calculated using the old `dp[j]` and `dp[j+1]` values, which correspond to the minimum paths from the row below.
   - `dp[j] = triangle[i][j] + min(dp[j], dp[j+1])`
6. **Result:** After the loops, `dp[0]` will hold the minimum total path sum.

## In-Place Dynamic Programming
If modifying the input `triangle` is permissible, we can achieve the ultimate space optimization by using the triangle itself as our DP table. This eliminates the need for any extra space apart from a few variables for iteration, resulting in O(1) extra space complexity.
**Time:** O(N^2) · **Space:** O(1)
**Pros:** Extremely space-efficient, using O(1) extra space.; Simple and concise implementation.; Retains the O(N^2) time efficiency.
**Cons:** This approach modifies the input data structure, which might be undesirable if the original triangle needs to be preserved for other purposes.
### Explanation
This is the most space-efficient approach. It uses the same bottom-up logic as the previous methods but cleverly reuses the input `triangle` list to store the intermediate DP values. We iterate from the second-to-last row upwards. For each element `triangle[i][j]`, we update its value to be the sum of its original value and the minimum of the two elements directly below it in the next row. By the time the process reaches the top row, the element `triangle[0][0]` will contain the overall minimum path sum.

```java
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();

        // Iterate from the second to last row up to the top
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                // Find the minimum of the two adjacent numbers in the row below
                int minSumBelow = Math.min(triangle.get(i + 1).get(j), triangle.get(i + 1).get(j + 1));
                
                // Update the current number with the sum of itself and the minimum from below
                int currentVal = triangle.get(i).get(j);
                triangle.get(i).set(j, currentVal + minSumBelow);
            }
        }

        // The top element of the triangle now holds the minimum path sum
        return triangle.get(0).get(0);
    }
}
```
### Algorithm
1. Iterate from the second-to-last row (`i = N-2`) up to the first row (`i = 0`).
2. For each row `i`, iterate through its elements from `j = 0` to `j = i`.
3. **In-place Update:** Calculate the minimum path sum from the current cell `(i, j)` by adding its value to the minimum of the two adjacent cells in the row below (`triangle[i+1][j]` and `triangle[i+1][j+1]`).
4. Update the value of `triangle[i][j]` with this new sum.
   - `triangle[i].set(j, triangle[i][j] + min(triangle[i+1][j], triangle[i+1][j+1]))`
5. **Result:** After the loops complete, the original top element `triangle[0][0]` will be overwritten with the minimum total path sum.

# Solutions
### Java

```java
class Solution {
public
  int minimumTotal(List<List<Integer>> triangle) {
    for (int i = triangle.size() - 2; i >= 0; --i) {
      for (int j = 0; j <= i; ++j) {
        int x = triangle.get(i).get(j);
        int y = Math.min(triangle.get(i + 1).get(j),
                         triangle.get(i + 1).get(j + 1));
        triangle.get(i).set(j, x + y);
      }
    }
    return triangle.get(0).get(0);
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumTotal(vector<vector<int>> &triangle) {
    for (int i = triangle.size() - 2; ~i; --i) {
      for (int j = 0; j <= i; ++j) {
        triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1]);
      }
    }
    return triangle[0][0];
  }
};

```

### Python

```python
class Solution : def minimumTotal ( self , triangle : List [ List [ int ]]) -> int : 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 ]) + triangle [ i ][ j ] ) return triangle [ 0 ][ 0 ]
```