Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Work bottom-up. Let dp[j] be the minimum path sum from row i's cell j down to the base. Initialize dp to the last row, then for each row above set dp[j] = triangle[i][j] + min(dp[j], dp[j+1]). The answer is dp[0]. This reuses the last row in place for O(n) space and O(n²) time; naive recursion is exponential.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you see that bottom-up DP eliminates the index-out-of-bounds cases that plague the top-down version, and that the whole triangle collapses into one array the width of its base.
Where candidates slip
Going top-down and mishandling the edges (cell j on a row can come from j-1 or j above, but those don't always exist), or summing the two children instead of taking the min.
How to stand out
Explain why bottom-up is cleaner here (children dp[j], dp[j+1] always exist), achieve O(n) space by overwriting the base row in place, and note it satisfies the classic O(n) extra-space follow-up.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewMin path sum apex to baseBrute force every descent?YesNoExplore the full treeCollapse the tree
How to read it:Folding from the base up, every cell (i, j) reads dp[j] and dp[j+1], both guaranteed to exist for j ≤ i. No boundary branches.
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 3
Brute Force — Recurse Both Children
1Hint 1Explore hintHide hint
From cell (i, j), the cheapest descent is this cell's value plus the cheaper of its two children: (i+1, j) and (i+1, j+1).
2Hint 2Explore hintHide hint
Write minPath(i, j) = triangle[i][j] + min(minPath(i+1, j), minPath(i+1, j+1)), starting from the apex (0, 0).
3Hint 3Explore hintHide hint
Base case: on the last row there's nothing below, so the cell returns just its own value.
A · Core idea
Translate the movement rule literally: standing on (i, j), you must step to one of the two cells diagonally below — (i+1, j) or (i+1, j+1) — so the best total from here is triangle[i][j] plus the cheaper of those two sub-descents.
Why this is the natural recurrence. The problem is a sequence of binary choices (lean left or right at each level), and min over the two recursive results captures 'pick the better choice'. Reasoning about the current cell and its two children, rather than entire paths, is what turns a path-enumeration question into a two-term recurrence.
Why the base case is the last row. Cells on the final row have no row beneath them, so their cheapest 'descent' is simply their own value — recursion bottoms out there cleanly.
Why we don't ship this. A triangle with n rows has 2^(n-1) distinct top-to-base paths, and the plain recursion explores essentially all of them, recomputing shared sub-descents over and over. Cell (i, j) is reached from many cells above and recomputed each time. For n = 200 that's astronomically slow. The overlap — the same (i, j) subproblem solved repeatedly — is the cue to cache.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
triangle = [[1],[2,3]]minPath(0,0)
1 + min(minPath(1,0), minPath(1,1))
branch left and right3C · Code with teaching comments
Reference implementation previewpublic int minimumTotal(List<List<Integer>> triangle) { return minPath(triangle, 0, 0); } private int minPath(List<List<Integer>> triangle, int i, int j) {Explore the full codeHide the full code
D · Why it works and complexityO(2ⁿ) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
Two cells on row i-1 (indices j-1 and j) both step down into cell (i, j), so the cheapest descent from (i, j) is shared and recomputed by each parent. That shared, parent-independent subproblem is precisely what dynamic programming caches — the future cost from a cell depends only on the cell, not on how you arrived.
ComplexityO(2ⁿ) time, O(n) space — Each call spawns two children and the recursion is n levels deep, so the call tree has about 2ⁿ nodes. Stack depth is O(n).
E · Edge cases and pitfalls5triangle = [[-10]] — Single row → i == n-1 immediately, returns -10.Explore edge casesHide edge cases
Edge cases handled
triangle = [[-10]]Single row → i == n-1 immediately, returns -10.two rowsApex recurses into two last-row leaves and picks the smaller — minimal exercise of the recurrence.
Pitfalls
- Recursing into (i+1, j-1) — there's no below-LEFT-of-j child; the two children are j and j+1.
- Summing left + right instead of taking the min — counts paths rather than optimizing.
- Shipping the recursion — exponential, hopeless for 200 rows.
Approach 2 of 3
Top-Down Memoization
1Hint 1Explore hintHide hint
How many distinct subproblems are there? Each is a cell (i, j), and a triangle of n rows has only ~n²/2 cells.
2Hint 2Explore hintHide hint
Add a memo indexed by (i, j). Return the cached descent cost if present; otherwise compute it once and store it.
3Hint 3Explore hintHide hint
Same recurrence as the recursion, now each cell's value is computed a single time.
A · Core idea
The recursion is correct but recomputes the descent from each cell many times. Since the cheapest descent from (i, j) is a fixed number, compute it once and remember it.
Why the state space is only quadratic. Every subproblem is a single cell (i, j), and the triangle has 1 + 2 + … + n = n(n+1)/2 cells. So although there are exponentially many paths, there are only O(n²) distinct subproblems. Caching by (i, j) therefore collapses the exponential recursion to O(n²) — the size of the cell set.
Why this is the gentlest first optimization. The code barely changes: add a cache lookup at the top and a write before the return. We still descend from the apex toward the base, so we don't have to reason about iteration order — the recursion finds a valid order itself. A sentinel (or a separate 'visited' marker) distinguishes 'not yet computed' from a legitimately small or negative cached value.
Why a careful sentinel matters here. Path sums can be negative (values go down to −10⁴), so you cannot use a value like 0 or −1 as 'uncomputed' — a real answer could equal it. Use a boxed Integer/null in Java or lru_cache in Python so the cache check is unambiguous. This is the one subtlety that distinguishes Triangle's memo from a positive-only problem like Climbing Stairs.
The payoff and the lingering cost. Memoization gives optimal O(n²) time, but still pays O(n²) space for the cache and O(n) stack. That's already acceptable, but the bottom-up version below removes the recursion and shrinks space to O(n) — exactly what the follow-up asks for.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
triangle = [[2],[3,4],[6,5,7]]solve(0,0)
2 + min(solve(1,0), solve(1,1))
memo = {}10C · Code with teaching comments
Reference implementation previewpublic int minimumTotal(List<List<Integer>> triangle) { int n = triangle.size(); Integer[][] memo = new Integer[n][n]; return solve(triangle, 0, 0, memo); }Explore the full codeHide the full code
D · Why it works and complexityO(n²) timeO(n²) spaceOpen the invariant and proofExplore the proofHide the proof
The leap from exponential to polynomial is a counting argument: exponentially many paths, but only O(n²) cells. Whenever the recursion's argument set is small even though its call tree is huge, memoization is guaranteed to collapse time to the size of that argument set. Recognizing 'how many distinct states exist?' is how you predict a DP's complexity.
ComplexityO(n²) time, O(n²) space — There are about n²/2 cells; each is solved once with O(1) work and cached → O(n²) time. The memo holds one value per cell → O(n²) space (plus O(n) recursion stack).
E · Edge cases and pitfalls5triangle = [[1]] — Apex is also the last row → base case returns 1 with no caching needed.Explore edge casesHide edge cases
Edge cases handled
triangle = [[1]]Apex is also the last row → base case returns 1 with no caching needed.n = 200Only ~20,100 cells are ever computed, each once — instant where the plain recursion would hang.
Pitfalls
- Using 0 or -1 as the 'uncomputed' sentinel — path sums can legitimately be 0 or negative, causing false cache hits.
- Placing the cache check after the recursive calls — it then prevents nothing.
- Forgetting to write the result before returning — stays exponential.
Approach 3 of 3 · Optimal
Bottom-Up — Collapse One Row at a Time (Optimal)
1Hint 1Explore hintHide hint
Flip the direction. Instead of cost-to-descend from a cell, compute it starting from the bottom: the last row's costs are just its values.
2Hint 2Explore hintHide hint
For a cell (i, j), its cheapest descent is triangle[i][j] + min(dp[j], dp[j+1]), where dp holds the row directly below.
3Hint 3Explore hintHide hint
Reuse one array initialized to the last row. Sweep rows upward, overwriting dp[j] left to right; the apex's answer ends in dp[0].
A · Core idea
Turn the recursion upside down. The cheapest descent from any last-row cell is simply its own value, so seed a 1D array dp with the entire bottom row. Then process rows from the second-to-last up to the apex: for each cell (i, j), its best descent is triangle[i][j] + min(dp[j], dp[j+1]), where dp[j] and dp[j+1] currently hold the cheapest descents of its two children one row below.
Why bottom-up erases every edge case. In a top-down fill you'd ask 'which cells above flow into (i, j)?' — and the answer depends on whether j is on a boundary (the leftmost cell has no upper-left parent, the rightmost no upper-right). Bottom-up asks instead 'which cells below does (i, j) flow into?' — always exactly dp[j] and dp[j+1], and for a cell on row i we have j ≤ i, so both indices are guaranteed in range. The branching is uniform; there are no special boundary cases to get wrong. That structural cleanliness is the real reason this problem is taught bottom-up.
Why one array suffices, with no diagonal trick. Each row only needs the row immediately below, so we keep just one array of length n (the base width). Crucially, when we compute dp[j] we read dp[j] (below-left) and dp[j+1] (below-right) and write to dp[j] — and we sweep j from left to right, so dp[j+1] is still the below row's value when we read it (we haven't reached it yet this pass). No saved-diagonal scalar is needed, unlike Edit Distance or Maximal Square; the in-place overwrite is naturally safe.
Why the final answer lands in dp[0]. After folding every row upward, dp[0] holds the cheapest descent from the apex — which is the whole triangle's minimum path sum. We can even mutate the triangle itself instead of a separate array, but a dedicated dp keeps the input intact.
Why this is the interview-grade solution. It's O(n²) time like the memo, but drops to O(n) space and removes recursion entirely — directly answering the stated follow-up. The narrative 'I'll solve it bottom-up so the children always exist and I only need one row' is exactly the maturity interviewers reward.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]Array state
init
dp = last row
11C · Code with teaching comments
D · Why it works and complexityO(n²) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
Reversing the direction of a DP can turn a boundary-laden mess into a clean uniform loop. Top-down here forces edge cases (which parents exist?); bottom-up makes every cell's two children always valid. When a top-down fill is full of if j == 0 / if j == width guards, try flipping it — the boundaries often vanish.
ComplexityO(n²) time, O(n) space — Each of the ~n²/2 cells is processed once with O(1) work → O(n²) time. A single array of length n (the base width) holds all needed state → O(n) space.
E · Edge cases and pitfalls5triangle = [[5]] — n = 1: dp = [5, 0], the upward loop never runs, returns dp[0] = 5.Explore edge casesHide edge cases
Edge cases handled
triangle = [[5]]n = 1: dp = [5, 0], the upward loop never runs, returns dp[0] = 5.all-negative trianglemin naturally chases the most negative descent; nothing special needed since we compare actual sums.
Pitfalls
- Sweeping rows top-to-bottom instead of bottom-up — reintroduces the boundary special cases this approach exists to avoid.
- Summing dp[j] + dp[j+1] instead of taking the min — counts paths rather than minimizing.
- Sizing dp to exactly n and reading dp[j+1] on the widest row — off-by-one out-of-bounds; pad to n+1 or copy the last row.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int minimumTotal(List<List<Integer>> triangle) { int n = triangle.size(); int[] dp = new int[n + 1]; for (int j = 0; j < n; j++) { dp[j] = triangle.get(n - 1).get(j);Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Top-down boundary mishandling
When filling downward, cell j on a row can be reached from j-1 or j above, but the leftmost cell has no j-1 parent and the rightmost no j parent. Forgetting those guards reads garbage. Bottom-up sidesteps it: children dp[j], dp[j+1] always exist.
Explore the code comparisonHide the code comparison
Top-down boundary mishandling
When filling downward, cell j on a row can be reached from j-1 or j above, but the leftmost cell has no j-1 parent and the rightmost no j parent. Forgetting those guards reads garbage. Bottom-up sidesteps it: children dp[j], dp[j+1] always exist.
Don't write this
// top-down: forgets that j-1 doesn't exist for the leftmost cell
dp[i][j] = triangle.get(i).get(j) + Math.min(dp[i - 1][j - 1], dp[i - 1][j]);Write this instead
// bottom-up: both children are always valid for j <= i
dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j + 1]);2Summing children instead of min
Triangle optimizes a path cost, so among the two children you keep the cheaper. Summing them solves a counting problem and explodes the value.
Explore the code comparisonHide the code comparison
Summing children instead of min
Triangle optimizes a path cost, so among the two children you keep the cheaper. Summing them solves a counting problem and explodes the value.
Don't write this
dp[j] = triangle[i][j] + dp[j] + dp[j + 1]Write this instead
dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])3Negative-unsafe memo sentinel
Values range down to -10⁴, so a path sum can be negative or zero. A 0 or -1 'uncomputed' marker collides with real answers and returns wrong cached values.
Explore the code comparisonHide the code comparison
Negative-unsafe memo sentinel
Values range down to -10⁴, so a path sum can be negative or zero. A 0 or -1 'uncomputed' marker collides with real answers and returns wrong cached values.
Don't write this
int[][] memo = new int[n][n]; // 0 default looks 'uncomputed' but 0 is a real answerWrite this instead
Integer[][] memo = new Integer[n][n]; // null is unambiguously 'uncomputed'Revise
Carry the pattern into the interview
Pattern to remember
Bottom-up path DP on a triangle
Code pattern to memorize
dp = last row of the triangle
for i from n-2 down to 0:
for j in 0..i:
dp[j] = triangle[i][j] + min(dp[j], dp[j+1])
answer = dp[0]Rules to remember
- 1From cell
(i, j)you may step to(i+1, j)or(i+1, j+1)— adjacent cells one row down — so the recurrence has exactly two children. - 2Going bottom-up is the trick: it removes all boundary special-casing because
dp[j]anddp[j+1]are always valid forj ≤ i. - 3Initialize
dpto the last row, then collapse upward; the final answer ends up indp[0]. - 4Take the min of the two children and add the current value — optimization, not counting.
- 5Reuse a single array of length n (the base width) and shrink the active prefix each row → O(n) space, with no rolling-diagonal bookkeeping.
Use this pattern when
- Cheapest / longest root-to-leaf path on a triangular or tree-like grid
- Each state branches to a small fixed set of next states one level down
- Collapsing a 2D structure to 1D by processing it level by level
- Optimizing an accumulated cost where the future depends only on the current cell
Choose another pattern when
- Counting paths instead of optimizing cost → sum the children, don't min
- Moves aren't restricted to adjacent cells below → general shortest-path / Dijkstra
- You need the actual path cells, not just the cost → backtrack through choices
- The structure is a real graph with cycles → BFS/DFS, not level DP
Interview takeaway
Triangle is the poster child for bottom-up DP: flip the natural top-down recursion upside down and every boundary headache disappears, leaving a clean O(n)-space collapse. The same 'process the last level first, fold upward' move solves many tree-DP and grid-path problems elegantly.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical bottom-up path DP on a layered structure. Recognize it when each cell branches to a small fixed set of cells in the next level and you optimize an accumulated cost. Flipping top-down to bottom-up removes boundary cases and enables O(n) space — the same idea drives Minimum Falling Path Sum and many tree DPs.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Minimum Path SumSame cheapest-path DP on a rectangular grid with right/down moves; O(n) rolling row.
- Minimum Falling Path SumComing soonSquare grid where each step goes to one of three cells below (j-1, j, j+1) — same bottom-up fold with three children.
- Minimum Falling Path Sum IIComing soonFalling path that can't reuse a column — track the two smallest values per row to stay O(n²).
- Unique PathsCounting cousin of grid path DP — sum the predecessors instead of taking the min.