Triangle
Given a triangle array triangle, return the minimum path sum from the top to the bottom.
For each step, you may move to an adjacent number in the row below.
More precisely, if you are at index i in the current row, you may move to either index i or index i + 1 in the next row.
Example 1
Input
n = 4
triangle =
[
[2],
[3, 4],
[6, 5, 7],
[4, 1, 8, 3]
]Output
11
Explanation
The minimum path is:
2 → 3 → 5 → 1
So:
2 + 3 + 5 + 1 = 11
Example 2
Input
n = 1
triangle =
[
[-10]
]Output
-10
Explanation
There is only one element in the triangle, so the only possible path is:
-10
Therefore, the minimum path sum is:
-10
Constraints
Hints:
Hint 1
For every position, choose the smaller of the two possible values directly below it.
Hint 2
Work from the bottom row upward.
For position j:
dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])
Author & Technical Reviewer
Technically reviewed by: ExamAdda Technical Review Team
Technical Reviewers, ExamAdda
Software engineers at ExamAdda who check every article's definitions, complexity claims and code examples before and after publishing.
Published
Aug 23, 2026
Last updated
Aug 23, 2026
Content Verification Methodology
Definitions and complexity claims were checked against authoritative computer-science references. Code examples were compiled and tested with standard, boundary and edge-case inputs.
Expected Output