Triangle
Last Updated: March 28, 2026
Understanding the Problem
We are given a triangle of numbers, and we need to find a path from the top to the bottom that gives the smallest possible sum. The catch is that from any position in the triangle, we can only move to the element directly below or to the element one position to the right on the row below. So this is not about picking the global minimum from each row, it is about finding a connected path that minimizes the total sum.
What makes this problem tricky is that a greedy approach (always pick the smaller neighbor below) does not work. Taking a slightly larger value now might open up a much cheaper path later. This is a classic signal for dynamic programming: optimal substructure (the best path through a cell depends on the best path from that cell downward) combined with overlapping subproblems (multiple paths from above converge on the same cell).
Key Constraints:
1 <= triangle.length <= 200--> The triangle has at most 200 rows, meaning up to about 20,000 elements total. An O(n^2) solution where n is the number of rows is perfectly fine.-10^4 <= triangle[i][j] <= 10^4--> Values can be negative. This rules out any approach that assumes all values are non-negative.triangle[i].length == triangle[i - 1].length + 1--> The triangle is well-formed. Row i has exactly i + 1 elements, so the adjacency rule always leads to valid positions.
Approach 1: Recursion (Brute Force)
Intuition
The most natural way to think about this problem is top-down. Starting at the apex of the triangle, at each cell we have two choices: go to the adjacent element below-left (same index on the next row) or below-right (index + 1 on the next row). We want the path that gives the smallest total sum.
So for each cell (row, col), the minimum path sum from that cell to the bottom is:
minPath(row, col) = triangle[row][col] + min(minPath(row + 1, col), minPath(row + 1, col + 1))
The base case is the last row, where the minimum path sum is just the cell's own value. This works correctly, but it explores every possible path through the triangle. From the top, there are 2 choices at each of the n - 1 levels, leading to 2^(n-1) paths.
Algorithm
- Define a recursive function
minPath(row, col)that returns the minimum path sum from cell(row, col)to the bottom of the triangle. - Base case: if
rowis the last row, returntriangle[row][col]. - Recursively compute the minimum path sum from
(row + 1, col)and(row + 1, col + 1). - Return
triangle[row][col]plus the smaller of those two results. - Call
minPath(0, 0)for the answer.
Example Walkthrough
Input:
The recursion explores all paths: 2->3->6->4, 2->3->6->1, 2->3->5->1, 2->3->5->8, 2->4->5->1, 2->4->5->8, 2->4->7->8, 2->4->7->3. The minimum is 2+3+5+1 = 11.
Code
- Time Complexity: O(2^n). At each of the n - 1 levels, we branch into 2 recursive calls, creating an exponential number of calls.
- Space Complexity: O(n). The recursion stack goes n levels deep (one for each row of the triangle).
The recursion recomputes the same cells over and over. What if we cached each result after computing it the first time?
Approach 2: Top-Down DP (Memoization)
Intuition
The brute force recurrence is correct, the problem is just that it recomputes the same subproblems many times. If we add a memo table to cache the result of minPath(row, col) after the first call, every subsequent call with the same (row, col) returns instantly.
The triangle has at most 1 + 2 + ... + n = n(n+1)/2 cells, so once every cell is computed once, we are done. This brings the time complexity from exponential down to O(n^2).
Algorithm
- Create a 2D memo table (or dictionary) to store computed results.
- Define
minPath(row, col): if the result is cached, return it. Base case: last row returns its value. Otherwise computetriangle[row][col] + min(minPath(row + 1, col), minPath(row + 1, col + 1)), cache and return. - Call
minPath(0, 0).
Example Walkthrough
Code
- Time Complexity: O(n^2). Each cell in the triangle is computed exactly once. The triangle has n(n+1)/2 cells, which is O(n^2).
- Space Complexity: O(n^2). The memo table stores one value per cell. The recursion stack adds O(n) but is dominated by the memo.
The time is now optimal, but we are using O(n^2) space for the memo table. Since each row only depends on the row below, can we compress to a single 1D array?
Approach 3: Bottom-Up DP (Optimal)
Intuition
Instead of starting from the top and working down recursively, we flip it around. Start from the bottom row and work upward. The minimum path sum from any cell in the bottom row is just the cell's value itself. For any cell above, the minimum path sum is the cell's value plus the smaller of the two minimum path sums from the row directly below.
The beauty of going bottom-up is that we only ever need the current row's results to compute the row above. So a single 1D array of size n is enough.
The 1D array reuse works because of a careful data dependency. When processing row row, we iterate col from 0 to row. At each step, dp[col] currently holds the minimum path sum from (row + 1, col) (the row below), and dp[col + 1] holds the sum from (row + 1, col + 1). After the update, dp[col] holds the minimum path sum from (row, col). Since we process columns left to right and each update only reads dp[col] and dp[col + 1], we never overwrite a value before it is needed.
Algorithm
- Initialize a DP array with the values from the bottom row of the triangle.
- Iterate from the second-to-last row up to row 0.
- For each cell
(row, col)in the current row, setdp[col] = triangle[row][col] + min(dp[col], dp[col + 1]). - After processing all rows, return
dp[0].
Example Walkthrough
Code
- Time Complexity: O(n^2). We process each cell in the triangle exactly once. The total number of cells is n(n+1)/2, which is O(n^2).
- Space Complexity: O(n). We use a single array of size n (the number of rows). This satisfies the follow-up requirement.