Triangle Min Path Sum LeetCode 120 Guide

LeetCode 120 Triangle gives you a triangular array of integers where each row has one more element than the row above it. Starting from the single element at the top (the apex), you move to an adjacent number on the row below at each step. An element at index j in row i is adjacent to elements at indices j and j+1 in row i+1. Your goal is to find the path from apex to base that minimizes the total sum of all elements along the path.

The triangle structure means the number of valid paths grows exponentially with depth — brute-force recursion without memoization would be O(2^n). This is a classic DP problem where overlapping subproblems allow polynomial-time solutions. The problem has two natural DP directions: top-down (apex to base) and bottom-up (base to apex). Both are correct, but bottom-up is considerably cleaner in practice.

Understanding the adjacency rule precisely is critical. Row i has i+1 elements (0-indexed). Element j in row i can move to element j or j+1 in row i+1. Equivalently, element j in row i can be reached from element j-1 or j in row i-1. This asymmetry is what makes top-down boundary handling tricky — and why bottom-up avoids it entirely.

The top-down DP defines dp[i][j] as the minimum path sum to reach element j in row i starting from the apex. The recurrence is dp[i][j] = triangle[i][j] + min(dp[i-1][j-1], dp[i-1][j]). At each position, you arrived from either the element directly above (same index, row above) or the element diagonally above-left (index j-1, row above). You add the current element's value to whichever predecessor had the smaller cost.

The boundary conditions complicate this direction. For the first element in each row (j=0), there is no dp[i-1][j-1] predecessor — you can only arrive from dp[i-1][0]. For the last element in each row (j=i), there is no dp[i-1][j] predecessor — you can only arrive from dp[i-1][j-1]. These edge cases require explicit checks or padding. After filling all rows, the answer is min(dp[n-1]).

With memoization (top-down recursion), you define solve(i, j) = triangle[i][j] + min(solve(i+1, j), solve(i+1, j+1)) with solve(n-1, j) = triangle[n-1][j] as the base. This avoids the explicit boundary handling by recursing downward — but still requires n²/2 memo slots and O(n) recursion depth. Top-down is instructive but the boundary cases make the iterative version less clean than the bottom-up alternative.

The bottom-up approach flips the direction: instead of propagating costs from the apex downward, start from the base row and work upward to the apex. Define dp[i][j] as the minimum path sum from element j in row i all the way to the bottom. The base case is the entire last row: dp[n-1][j] = triangle[n-1][j] for all j. The recurrence going upward is dp[i][j] = triangle[i][j] + min(dp[i+1][j], dp[i+1][j+1]).

This direction is cleaner because the adjacency rule is now symmetric at every position. From element j in row i, you always have exactly two valid successors: dp[i+1][j] (same index in the next row) and dp[i+1][j+1] (next index in the next row). There is no first-element or last-element special case — both indices are always valid because row i+1 has i+2 elements when row i has i+1 elements. The boundaries naturally disappear.

After propagating all the way up, the answer sits at dp[0][0] — the single element at the apex, now storing the minimum cost path from top to bottom. No need to scan the final row for a minimum. This makes the answer extraction trivial and the logic end-to-end cleaner than the top-down version.

The elegance of bottom-up for the Triangle problem comes from the asymmetry of adjacency. When moving downward (top-down), element j at row i can only move to j or j+1 — but element j at row i can be reached from j-1 or j at row i-1. This means the first element (j=0) only has one predecessor (j=0 above) and the last element (j=i) only has one predecessor (j=i-1 above). You must handle two special cases.

When moving upward (bottom-up), element j at row i always has exactly two successors: j and j+1 at row i+1. Row i has i+1 elements (indices 0..i) and row i+1 has i+2 elements (indices 0..i+1), so both j and j+1 are always valid indices in the next row. No boundary check is ever needed. Every position in the interior and at the edges of each row follows the same recurrence.

This is a general pattern in DP: choosing the direction that makes boundary conditions trivially satisfied often simplifies the code significantly. For Triangle specifically, the bottom-up direction aligns the recurrence with the wider row always being below the narrower row, so index validity is guaranteed by the triangular structure itself. The answer landing at dp[0][0] is a bonus that avoids a post-processing scan.

The 2D bottom-up DP uses O(n²/2) space for the dp table. But notice that when computing row i from row i+1, you only ever reference the row immediately below — dp[i+1][j] and dp[i+1][j+1]. This means a single 1D array of length n (the number of rows, equal to the length of the last row) is sufficient. Initialize it to the base row, then update it in-place as you move upward.

For each row i from n-2 down to 0, iterate j from 0 to i inclusive: dp[j] = triangle[i][j] + min(dp[j], dp[j+1]). Here dp[j] (before update) is the cost from the row below at index j, and dp[j+1] (not yet updated in this inner loop iteration for j) is the cost from the row below at index j+1. Because we iterate j from left to right and only read dp[j+1] which is updated later, there is no overwrite conflict.

After processing row i, indices 0 through i of dp hold the minimum costs for that row. Indices beyond i are stale values from the previous pass but are never read again (the inner loop for row i only reads up to j=i+1). After all rows are processed, dp[0] holds the answer. This 1D in-place update reduces space from O(n²) to O(n) with no loss in correctness.

Python (bottom-up O(n) space): n = len(triangle); dp = triangle[-1][:]; for i in range(n-2, -1, -1): for j in range(i+1): dp[j] = triangle[i][j] + min(dp[j], dp[j+1]); return dp[0]. This is 5 lines of core logic. The copy triangle[-1][:] initializes dp to the base row. The double loop counts down rows and across each row left to right. Time O(n²), space O(n).

Java (bottom-up O(n) space): int n = triangle.size(); int[] dp = triangle.get(n-1).stream().mapToInt(Integer::intValue).toArray(); for (int i = n-2; i >= 0; i--) { List<Integer> row = triangle.get(i); for (int j = 0; j <= i; j++) { dp[j] = row.get(j) + Math.min(dp[j], dp[j+1]); } } return dp[0];. Same logic — initialize to last row, work upward, return dp[0]. Both solutions have identical O(n²) time and O(n) space.

The core insight in both implementations is that the inner loop runs j from 0 to i inclusive, and reads dp[j+1] before dp[j] is overwritten. Since j increments from left to right and we only read dp[j+1] (which is updated in a later iteration), the in-place update is safe. Compare this to the top-down version, which needs separate arrays for each row to avoid overwriting predecessors prematurely.

Triangle (LeetCode 120) is closely related to Minimum Path Sum (LeetCode 64), which uses a rectangular grid instead of a triangle. Both problems involve finding a minimum-cost path with constrained moves and both benefit from 1D space optimization. The key difference is that Minimum Path Sum moves right-or-down while Triangle moves to adjacent indices on the next row — but the DP formulation is structurally identical.

Dungeon Game (LeetCode 174) extends grid DP with a health constraint: the knight must maintain positive HP throughout. This forces reverse DP (bottom-right to top-left) for the same reason bottom-up is preferred for Triangle — the constraint depends on the future, so you must propagate from the end. Falling Path Sum (LeetCode 931) generalizes Triangle to a square matrix with three adjacency choices instead of two, but uses the same bottom-up structure.

Understanding Triangle builds your intuition for the entire grid DP family: recognize when boundary conditions suggest flipping DP direction, when a 1D rolling array suffices by noting which rows are accessed, and how the answer position changes with direction (dp[0][0] for bottom-up vs min(dp[n-1]) for top-down). These three instincts transfer directly to Minimum Path Sum, Dungeon Game, Falling Path Sum, and Cherry Pickup.