Given a triangle array, return the minimum path sum from top to bottom.
For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.
Example 1:
Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] Output: 11 Explanation: The triangle looks like: 2 3 4 6 5 7 4 1 8 3 The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).
Example 2:
Input: triangle = [[-10]] Output: -10
Constraints:
1 <= triangle.length <= 200triangle[0].length == 1triangle[i].length == triangle[i - 1].length + 1-104 <= triangle[i][j] <= 104Follow up: Could you do this using only
O(n) extra space, where n is the total number of rows in the triangle?Problem Overview: You are given a triangular array where each row has one more element than the previous row. Starting at the top, move to adjacent numbers in the row directly below and compute the minimum possible path sum from top to bottom.
Approach 1: Top-Down Dynamic Programming with Memoization (Time: O(n^2), Space: O(n^2))
This approach treats the triangle as a recursive decision tree. From position (row, col), you can move to (row+1, col) or (row+1, col+1). Use recursion to compute the minimum path sum from the current cell to the bottom, and store results in a memo table so each subproblem is solved once. Memoization eliminates repeated work that appears in naive recursion. This approach is intuitive if you naturally think about exploring paths top‑down and caching results.
Approach 2: Bottom-Up Dynamic Programming (2D DP) (Time: O(n^2), Space: O(n^2))
Instead of exploring paths recursively, build the solution from the bottom row upward. Create a DP table where dp[row][col] stores the minimum path sum from that position to the bottom. For each cell, compute triangle[row][col] + min(dp[row+1][col], dp[row+1][col+1]). Because each value depends only on the row below, iterating from the second-last row to the top fills the table efficiently. This converts the recursive idea into a clean iterative dynamic programming solution.
Approach 3: Bottom-Up Dynamic Programming (Space Optimized) (Time: O(n^2), Space: O(n))
The DP transition only depends on the next row, so a full 2D table is unnecessary. Copy the last row into a 1D array and update it while moving upward through the triangle. For each element, update dp[col] = triangle[row][col] + min(dp[col], dp[col+1]). The array always represents the minimum path sums for the row below the current one. This keeps the same time complexity while reducing memory usage to linear space. The triangle itself is just an array structure, while the optimization relies on recognizing overlapping subproblems typical in dynamic programming.
Recommended for interviews: The bottom-up dynamic programming solution with 1D optimization is what interviewers usually expect. It demonstrates that you understand DP transitions and space optimization. Explaining the top-down memoization version first can help show how you derived the recurrence before converting it into the optimal iterative form.
In this approach, we'll use dynamic programming (DP) to achieve the solution. We'll start from the bottom of the triangle and minimize the sum path to the top. We'll keep updating the path sum in a DP array as we move to the top row.
The function minimumTotal takes a 2D array representing the triangle and its size and calculates the minimum path sum using a bottom-up DP strategy. We utilize an array dp which holds the path sums for the current row. We iterate from the last row to the first, updating dp till the top.
Time Complexity: O(n^2), where n is the number of rows in the triangle.
Space Complexity: O(n), due to the use of the array dp.
This approach uses a top-down strategy with memoization to store already computed results, avoiding redundant calculations. Each recursive call stores the minimum path sum starting from the current index down to the base of the triangle.
This C code applies a memoization approach, leveraging recursion through dfs to calculate and store intermediate results in memo, exploring both potential paths per cell.
Time Complexity: O(n^2) (due to memoization)
Space Complexity: O(n^2) for memoization storage.
We define f[i][j] as the minimum path sum from the bottom of the triangle to position (i, j). Here, position (i, j) refers to the position in row i and column j of the triangle (both indexed from 0). We have the following state transition equation:
$
f[i][j] = min(f[i + 1][j], f[i + 1][j + 1]) + triangle[i][j]
The answer is f[0][0]$.
We notice that the state f[i][j] only depends on states f[i + 1][j] and f[i + 1][j + 1]. Therefore, we can use a one-dimensional array instead of a two-dimensional array, reducing the space complexity from O(n^2) to O(n).
The time complexity is O(n^2), and the space complexity is O(n), where n is the number of rows in the triangle.
| Approach | Complexity |
|---|---|
| Dynamic Programming Bottom-Up Approach | Time Complexity: |
| Top-Down Dynamic Programming with Memoization | Time Complexity: |
| Dynamic Programming | — |
| Dynamic Programming (Space Optimization) | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Top-Down DP with Memoization | O(n^2) | O(n^2) | When reasoning recursively about paths and caching overlapping subproblems |
| Bottom-Up DP (2D table) | O(n^2) | O(n^2) | Clear iterative implementation that mirrors the DP recurrence |
| Bottom-Up DP (1D optimized) | O(n^2) | O(n) | Preferred approach when minimizing extra memory in interviews |
Triangle - Dynamic Programming made Easy - Leetcode 120 • NeetCode • 66,360 views views
Watch 9 more video solutions →Practice Triangle with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor