Find the minimum path sum from the top to the bottom of a triangle of numbers.
Triangle Minimum Path Sum
gfgProblem
You are given a triangular array of integers. Start at the top element and move to the next row one step at a time. From position i in a row, you may move to either of the two adjacent positions in the row below.
Return the minimum possible sum of values along any path from the top to the bottom.
Notes
- Each move must go to an adjacent number in the next row.
- The triangle has exactly one element in the first row, two in the second, and so on.
- You must choose one number from each row.
Input Format
- An integer triangle
triangle, wheretriangle[r]containsr + 1integers. - The first row contains the starting value.
Output Format
- Return a single integer: the minimum path sum from top to bottom.
Constraints
1 <= triangle.length- Each row
rhas exactlyr + 1elements - Values may be negative, zero, or positive integers
- The answer fits in a 32-bit signed integer
Example 1
Input
triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output
11
Explanation
The minimum path is 2 -> 3 -> 5 -> 1, which sums to 11.
Example 2
Input
triangle = [[-10]]
Output
-10
Explanation
There is only one path, so the answer is the single value.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.