Watch 10 video solutions for Triangle, a medium level problem involving Array, Dynamic Programming. This walkthrough by take U forward has 253,126 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 triangle array where each row has one more element than the previous. Starting at the top, move to adjacent numbers on the row below and compute the minimum path sum from top to bottom.
The key constraint: from index i in row r, you can only move to i or i+1 in row r+1. Brute forcing every path quickly explodes in complexity, so the problem naturally leads to dynamic programming where overlapping subproblems are reused.
Approach 1: Top-Down Dynamic Programming with Memoization (Time: O(n²), Space: O(n²))
Start from the top element and recursively explore the two valid moves to the next row. At each position (row, col), compute the minimum cost of continuing down the triangle. Without caching, the same subtrees get recomputed many times. Memoization fixes this by storing results in a DP table indexed by (row, col). When the recursion revisits a state, return the stored value instead of recomputing. This converts an exponential recursion into an efficient solution that processes each cell once.
The recursive relation is: triangle[row][col] + min(down, diagonal). This approach maps closely to the problem definition and is easy to reason about if you're comfortable with recursion.
Approach 2: Dynamic Programming Bottom-Up (Time: O(n²), Space: O(n))
Instead of starting from the top, work upward from the last row. The last row already represents the minimum path sums from those nodes to the bottom. Maintain a DP array initialized with the last row values. Then iterate from the second-last row upward, updating each position with triangle[row][col] + min(dp[col], dp[col+1]). Each update represents choosing the cheaper of the two reachable children.
This method processes the triangle level by level and reuses a single array, reducing memory usage to O(n) where n is the width of the bottom row. Since every element is visited once, the total runtime is O(n²). The approach relies on simple iteration and fits naturally with array traversal.
Recommended for interviews: The bottom-up dynamic programming solution is usually expected. It runs in optimal O(n²) time with O(n) space and demonstrates strong DP intuition. Showing the recursive memoized version first can highlight how the problem decomposes into subproblems, but finishing with the bottom-up optimization signals deeper mastery.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Recursion | O(2^n) | O(n) | Conceptual baseline to understand all possible paths |
| Top-Down DP (Memoization) | O(n^2) | O(n^2) | When recursion is easier to reason about and caching overlapping subproblems |
| Bottom-Up DP (Optimized) | O(n^2) | O(n) | Best general solution with minimal memory usage |