# Triangle

Updated: Apr 23, 2021

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:
__23__ 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?

**Solution:**

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