Watch 10 video solutions for Triangle, a medium level problem involving Array, Dynamic Programming. This walkthrough by NeetCode has 66,360 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |