#120 Triangle
frequently reported atBloombergAmazonMicrosoftGoogleGoldman Sachs
the problem
In plain words
A triangle of numbers has 1 number in row 0, 2 in row 1, and so on. Start at the top. From index i in one row you may step to index i or i + 1 in the next row. Return the smallest possible sum of a path from the top to the bottom row.
in triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
out 11
2 + 3 + 5 + 1.
in triangle = [[-10]]
out -10
- 1 ≤ triangle.length ≤ 200
- Row 0 has 1 number; each row is one longer than the row above
- −10⁴ ≤ triangle[i][j] ≤ 10⁴
- Follow-up: O(n) extra space, where n is the number of rows
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternGrid DP
Work from the bottom up. The cheapest path from (r, i) down is its own value plus the cheaper of the two cells below it. The bottom row is the base case, and the single top cell ends up holding the answer — no edge cases, no min over the last row.
solutions
From brute force to optimal
best(r, i) = value + min(best(r + 1, i), best(r + 1, i + 1)); the bottom row returns its value.
- Start at best(0, 0).
- Try both cells below, keep the cheaper.
Two choices per row: 2ⁿ⁻¹ different paths for n rows.
Recursion depth = number of rows.
class Solution { public int minimumTotal(List<List<Integer>> triangle) { return best(triangle, 0, 0); } /** Cheapest path sum from (row, i) down to the bottom row. */ private int best(List<List<Integer>> triangle, int row, int i) { int here = triangle.get(row).get(i); if (row == triangle.size() - 1) return here; // bottom row: nothing below return here + Math.min(best(triangle, row + 1, i), best(triangle, row + 1, i + 1)); }}Only n(n + 1)/2 cells exist — cache best(r, i).
- Integer[][] memo, null = unknown (sums can be 0 or negative).
- Check, compute, store.
n(n + 1)/2 cells, each computed once.
The memo (plus O(n) stack).
class Solution { public int minimumTotal(List<List<Integer>> triangle) { int n = triangle.size(); Integer[][] memo = new Integer[n][n]; // null = not computed (sums can be 0 or negative) return best(triangle, 0, 0, memo); } private int best(List<List<Integer>> triangle, int row, int i, Integer[][] memo) { int here = triangle.get(row).get(i); if (row == triangle.size() - 1) return here; if (memo[row][i] != null) return memo[row][i]; return memo[row][i] = here + Math.min(best(triangle, row + 1, i, memo), best(triangle, row + 1, i + 1, memo)); }}dp starts as the bottom row; climb up, replacing dp[i] with value + min(dp[i], dp[i + 1]).
- dp = copy of the last row.
- For r = n − 2 down to 0, for i = 0..r: dp[i] = triangle[r][i] + min(dp[i], dp[i + 1]).
- Return dp[0].
Every cell is visited once.
One array as long as the bottom row.
class Solution { public int minimumTotal(List<List<Integer>> triangle) { int n = triangle.size(); int[] dp = new int[n]; // dp[i] = cheapest path from (row, i) to the bottom for (int i = 0; i < n; i++) dp[i] = triangle.get(n - 1).get(i); // start with the bottom row for (int row = n - 2; row >= 0; row--) { // climb up one row at a time for (int i = 0; i <= row; i++) { // left to right: dp[i + 1] is still the row below dp[i] = triangle.get(row).get(i) + Math.min(dp[i], dp[i + 1]); } } return dp[0]; // the apex }}in the room
How to say it in the interview
talk track
- "Top-down needs a min over the whole last row and edge checks; bottom-up ends in a single cell."
- Show dp[i] = row[i] + min(dp[i], dp[i + 1]) and why left to right is safe: dp[i + 1] still holds the row below when you read it.
- Mention that greedy fails: the cheaper next step can lead into an expensive row.
traps
- Greedy (always step to the smaller child) fails: [[1],[2,3],[100,100,4]] → greedy pays 103, the best is 8.
- Using 0 as "not computed" in a memo — sums can be 0 or negative; use Integer[][] with null.
- Updating right to left in the one-row version overwrites dp[i + 1] before it's read.
what they ask next
Follow-ups
Return the path itself?
Keep the full table (or the choice made at each cell) and walk down from the top, always to the child that gave the minimum.
O(1) extra space?
Only if you may overwrite the input: update the triangle's rows in place, bottom-up.
before you submit
Edge cases to test
- One row → its only number (it can be negative).
- Negative numbers everywhere: the answer is just the most negative path — nothing to prune.
- Greedy trap: [[1],[2,3],[100,100,4]] → 8.
practise next
Similar problems
- #64Minimum Path SumMediumin Dynamic Programming
- #62Unique PathsMediumin Dynamic Programming