Triangle
Problem Statement
You are given a triangle array. Starting at the top, move to adjacent numbers on the row below. Return the minimum path sum from the top to any value in the last row.
Input
A list of rows triangle, where row i has i + 1 integers.
Output
An integer: the minimum total from the top row to the bottom row using adjacent downward moves.
Constraints
- •
1 <= triangle.length <= 200 - •
triangle[0].length == 1 - •
triangle[i].length == triangle[i - 1].length + 1 - •
-10^4 <= triangle[i][j] <= 10^4
Examples
Example 1
triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
11Example 2
triangle = [[-10]]
-10Learning Objectives
- Recognise that each triangle position has two possible children in the next row.
- Define a bottom-up state as the minimum suffix cost from a cell to the bottom.
- Use the last row as the base case for upward processing.
- Compress the DP to a single row of length equal to the triangle height.
Intuition
A forward view asks for the cheapest cost to reach each position from the top. That works, but it needs careful edge handling because each row has a different length.
The cleaner interview solution looks from the bottom upward. If you already know the minimum cost from each child to the bottom, then the best path from the current value is simply the current value plus the cheaper child. By the time you reach the top, the whole triangle has collapsed into one number.
This is why a 1D array is natural. dp[j] and dp[j + 1] represent the two child choices directly below the current cell. Updating dp[j] from left to right within a row is safe because both child values come from the row below before they are overwritten for this row.
Common mistakes
- ×Using the rectangular grid recurrence with top and left neighbours; a triangle cell depends on two adjacent children when solved bottom-up.
- ×Returning the minimum value in the last row after a top-down pass without ensuring all path sums were updated correctly.
- ×Processing bottom-up from right to left and then accidentally reading an already-updated child value.
- ×Forgetting that values can be negative, so greedy local choices from the top are not reliable.
State Definition
Let dp[i][j] be the minimum path sum starting at triangle cell (i, j) and ending anywhere in the last row. The answer is dp[0][0].
For the compressed version, after processing row i, dp[j] stores that same minimum suffix sum for cell (i, j).
State Transition
Base case: every last-row state is the cell value itself, so dp[last][j] = triangle[last][j].
For rows above the last row:
dp[i][j] = triangle[i][j] + min(dp[i + 1][j], dp[i + 1][j + 1])
In the 1D version, process rows from bottom to top and update dp[j] = triangle[i][j] + min(dp[j], dp[j + 1]). Before the update, dp[j] and dp[j + 1] are the two child costs from the row below.
Solutions
Solution: Bottom-up 1D DP
Collapse the triangle from the bottom row upward. A sentinel-sized array starts at zero below the triangle, and each row overwrites the entries that correspond to its cells.
Step-by-step
- Let n be the number of rows and create best with length n + 1 filled with zero.
- Iterate row from n - 1 down to 0.
- For each column in that row, compute the current value plus the smaller of the two child costs best[col] and best[col + 1].
- Store the result back into best[col].
- After the top row is processed, return best[0].
O(n^2)
O(n)
The number of triangle entries is O(n^2), and the DP stores one row of child costs.
Java implementation
Dry Run
Sample input
triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]. The array has one extra sentinel zero at the end.
| row | values | best before row | updates | best after row |
|---|---|---|---|---|
| 3 | [4,1,8,3] | [0,0,0,0,0] | 4+min(0,0), 1+min(0,0), 8+min(0,0), 3+min(0,0) | [4,1,8,3,0] |
| 2 | [6,5,7] | [4,1,8,3,0] | 6+min(4,1)=7, 5+min(1,8)=6, 7+min(8,3)=10 | [7,6,10,3,0] |
| 1 | [3,4] | [7,6,10,3,0] | 3+min(7,6)=9, 4+min(6,10)=10 | [9,10,10,3,0] |
| 0 | [2] | [9,10,10,3,0] | 2+min(9,10)=11 | [11,10,10,3,0] |
After the top row collapses, best[0] = 11. Each row reuses the row below as its two-child lookup table.
Complexity Analysis
A triangle with n rows contains O(n^2) values, so reading all values already costs O(n^2). The bottom-up row compression keeps auxiliary space to O(n).
Bottom-up 1D DP
O(n^2)
O(n)
The number of triangle entries is O(n^2), and the DP stores one row of child costs.
Interview Tips
Lead with the bottom-up interpretation. It avoids awkward top-row edge cases and makes the transition almost visual: current value plus the cheaper of the two children below. Emphasise that negative numbers defeat greedy choices, but not DP, because DP keeps the full best suffix for every position.
Likely follow-ups
- How would you solve it top-down with memoization?
- How would you reconstruct the actual minimum path values?
- What if each move could go to any of the next row positions within distance two?
- Can you update the triangle in place if mutation is allowed?
Similar Problems
Key Takeaways
- Triangle DP can be solved cleanly by defining the state as minimum suffix cost.
- Bottom-up processing turns each cell into current value plus the cheaper child.
- The last row is the natural base case because no more moves are needed there.
- A single array is enough because each row only needs the row directly below it.