# 120 Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

```
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
```

The minimum path sum from top to bottom is`11`(i.e.,2+3+5+1= 11).

**Note:**\
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

**Complexity:** O(n) time, O(2sqrt(n)) space. Given N elements in the triangle matrix, I add 0s to both ends of matrix).

**The Idea:** Build an accumulation matrix (dynamic programming) that follows the rule of what is considered to be an adjacent element. To make things easier for ourselves, we add `INT_MAX` to both ends of our triangle matrix (`refine_triangle_matrix`). Keep in mind that this doubles the time complexity of our code, but we do this as a hack in order to avoid having to define separate subroutines for the edges of the triangle. Instead, we define a single subroutine that iterates through this new matrix. The minimum sum then follows to be minimum element in the bottom row.

This would be the accumulation matrix for the example above.

```
0:    2147483647  2 2147483647
1:    2147483647  5  6 2147483647
2:    2147483647 11 10 13 2147483647
3:    2147483647 15 11 18 16 2147483647
```

Related algorithms: Seam Carving (computer vision)

```cpp
void refine_triangle_matrix(vector<vector<int>> &triangle)
{
    if (triangle.empty()) return;

    const size_t col_size = triangle.size();
    const size_t row_size = triangle.at(0).size();

    // inserting int max since we are minimizing the
    // entire thing (hence these additions get ignored)
    for (int i = 0; i < col_size; i++) {
        triangle.at(i).push_back(INT_MAX);
        auto it = triangle.at(i).begin();
        triangle.at(i).insert(it, INT_MAX);
    }
}

int minimumTotal(vector<vector<int>>& triangle) 
{
    if (triangle.empty()) return 0;

    refine_triangle_matrix(triangle);
    const size_t col_size = triangle.size();

    for (int i = 1; i < col_size; i++) {
        for (int j = 1; j < triangle.at(i).size() - 1; j++) {
            int top_left = triangle[i - 1][j - 1];
            int top_right = triangle[i - 1][j];
            triangle[i][j] += min(top_left, top_right);
        }
    }
    //print2d(triangle); pause();
    return *min_element(triangle.at(col_size - 1).begin() + 1, triangle.at(col_size - 1).end() - 1);
}

// testing
int main()
{
    vector<vector<int>> tri = 
    {
        { 2 },
        { 3,4 },
        { 6,5,7 },
        { 4,1,8,3 }
    };

    cout << minimumTotal(tri) << endl;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/120-triangle.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.