> For the complete documentation index, see [llms.txt](https://maksimdan.gitbook.io/interview-practice-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/120-triangle.md).

# 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
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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, and the optional `goal` query parameter:

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

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

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.