Triangle — Solution in Python, Java & C++
Triangle solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon and Google.
Triangle is a medium coding problem on arrays and dynamic programming, asked in Amazon, Google, Adobe and Bloomberg interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon, Google, Adobe, Bloomberg
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a triangle array, return the minimum path sum from top to bottom.
At each step you may move to an adjacent number on the row below: from index i on the current row you may move to index i or i + 1 on the next.
Example 1
Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: The path 2 → 3 → 5 → 1 sums to 11.
Example 2
Input: triangle = [[-10]]
Output: -10
Example 3
Input: triangle = [[1],[2,3]]
Output: 3
Constraints
1 <= triangle.length <= 8triangle[i].length == i + 1-100 <= triangle[i][j] <= 100
Follow-up: Can you do it using only O(n) extra space, where n is the number of rows?
Hints for Triangle
Hint 1
Working top-down forces you to track every partial path; working bottom-up collapses them.
Hint 2
Start with the last row as the answer for each of its cells, then fold each row above into it.
Hint 3
One array the width of the base is enough, overwritten in place from left to right.
How to solve Triangle
Fold bottom-up: start with the last row as the answer for its cells, and for each row above set dp[c] = triangle[r][c] + min(dp[c], dp[c+1]).
Approach
- Copy the last row into
dp. - For
rfrom the second-last row up to 0, updatedp[c]forcin0..r. - Return
dp[0].
Why it works
From cell (r, c) the path continues to (r+1, c) or (r+1, c+1), so the best cost from that cell downward is its value plus the better of the two below. Bottom-up leaves the answer at the apex with one array.
Complexity
- Time —
O(n²) - Space —
O(n)
Pitfalls
- Top-down needs care at the row edges; bottom-up has no edge cases.
Reference solution
Python
def minimumTotal(triangle) -> int:
dp = list(triangle[-1])
for r in range(len(triangle) - 2, -1, -1):
for c in range(r + 1):
dp[c] = triangle[r][c] + min(dp[c], dp[c + 1])
return dp[0]Java
public static int minimumTotal(int[][] triangle) {
int n = triangle.length;
int[] dp = Arrays.copyOf(triangle[n - 1], n);
for (int r = n - 2; r >= 0; r--) {
for (int c = 0; c <= r; c++) {
dp[c] = triangle[r][c] + Math.min(dp[c], dp[c + 1]);
}
}
return dp[0];
}C++
int minimumTotal(vector<vector<int>>& triangle) {
int n = (int) triangle.size();
vector<int> dp = triangle[n - 1];
for (int r = n - 2; r >= 0; r--) {
for (int c = 0; c <= r; c++) {
dp[c] = triangle[r][c] + min(dp[c], dp[c + 1]);
}
}
return dp[0];
}JavaScript
var minimumTotal = function(triangle) {
const n = triangle.length;
const dp = triangle[n - 1].slice();
for (let r = n - 2; r >= 0; r--) {
for (let c = 0; c <= r; c++) {
dp[c] = triangle[r][c] + Math.min(dp[c], dp[c + 1]);
}
}
return dp[0];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming