Log inSign up
mediumLeetCodeNot Started

Triangle Minimum Path Sum

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on LeetCode
Lesson

Problem Statement

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: ``text triangle = [ [2], [3, 4], [6, 5, 7], [4, 1, 8, 3] ] ` - **Output**: 11 - **Explanation**: The path 2 -> 3 -> 5 -> 1` minimizes the sum (2 + 3 + 5 + 1 = 11).

### Example 2 - Input: triangle = [[-10]] - Output: -10

Constraints:

  • 1 <= triangle.length <= 200
  • triangle[0].length == 1
  • triangle[i].length == triangle[i - 1].length + 1
  • -104 <= triangle[i][j] <= 104

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Compare top-down vs bottom-up approaches on triangular grids.
  • Eliminate boundary edge cases by reversing traversal direction.
  • Space-optimize to a 1D array of length n.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Triangular grid structure.
  • Moves from (r, c) to (r+1, c) or (r+1, c+1).
  • Path sum minimization.

Algorithmic Decision Tree:

  • Bottom-up tabulation avoids finding the minimum across the entire bottom row.

Connected Patterns:

Minimum Path SumMaximum Path Sum in MatrixGold Mine Problem

1. Recursive Top-Down DFS

Intuition

Recursively explore both moves (i and i + 1) from the top cell down to the base row.

Algorithm

  1. Define solve(r, c).
  2. If r == n - 1, return triangle[r][c].
  3. Return triangle[r][c] + min(solve(r + 1, c), solve(r + 1, c + 1)).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 int solve(int r, int c, const vector<vector<int>>& triangle) {
9 if (r == triangle.size() - 1) return triangle[r][c];
10 return triangle[r][c] + min(solve(r + 1, c, triangle), solve(r + 1, c + 1, triangle));
11 }
12public:
13 int minimumTotal(vector<vector<int>>& triangle) {
14 return solve(0, 0, triangle);
15 }
16};
17
18int main() {
19 Solution sol;
20 vector<vector<int>> triangle = {{2}, {3, 4}, {6, 5, 7}, {4, 1, 8, 3}};
21 cout << "Min Path: " << sol.minimumTotal(triangle) << endl;
22 return 0;
23}

Time & Space Complexity

  • Time complexity: O(2^n)
  • Space complexity: O(n) call stack

2. Memoized Top-Down DP

Intuition

Store subproblem answers for (r, c) in a memoization table.

Algorithm

  1. Initialize memo matrix matching triangle dimensions with \infty.
  2. In solve(r, c): return memo[r][c] if already computed.
  3. Save and return memo[r][c].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 int solve(int r, int c, const vector<vector<int>>& triangle, vector<vector<int>>& memo) {
9 if (r == triangle.size() - 1) return triangle[r][c];
10 if (memo[r][c] != 1e9) return memo[r][c];
11 return memo[r][c] = triangle[r][c] + min(solve(r + 1, c, triangle, memo), solve(r + 1, c + 1, triangle, memo));
12 }
13public:
14 int minimumTotal(vector<vector<int>>& triangle) {
15 int n = triangle.size();
16 vector<vector<int>> memo(n, vector<int>(n, 1e9));
17 return solve(0, 0, triangle, memo);
18 }
19};
20
21int main() {
22 Solution sol;
23 vector<vector<int>> triangle = {{2}, {3, 4}, {6, 5, 7}, {4, 1, 8, 3}};
24 cout << "Min Path: " << sol.minimumTotal(triangle) << endl;
25 return 0;
26}

Time & Space Complexity

  • Time complexity: O(n^2)
  • Space complexity: O(n^2)

3. Bottom-Up 1D DP Tabulation

Intuition

Initialize a 1D array with the bottom row of the triangle. Traverse upwards to row 0, updating dp[c] = triangle[r][c] + min(dp[c], dp[c+1]).

Algorithm

  1. Initialize 1D array dp with the last row of the triangle.
  2. For r from n - 2 down to 0:
  3. For c from 0 to r:
  4. dp[c] = triangle[r][c] + min(dp[c], dp[c + 1]).
  5. Return dp[0].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int minimumTotal(vector<vector<int>>& triangle) {
10 int n = triangle.size();
11 vector<int> dp = triangle.back();
12
13 for (int r = n - 2; r >= 0; --r) {
14 for (int c = 0; c <= r; ++c) {
15 dp[c] = triangle[r][c] + min(dp[c], dp[c + 1]);
16 }
17 }
18
19 return dp[0];
20 }
21};
22
23int main() {
24 Solution sol;
25 vector<vector<int>> triangle = {{2}, {3, 4}, {6, 5, 7}, {4, 1, 8, 3}};
26 cout << "Min Path: " << sol.minimumTotal(triangle) << endl;
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(n^2)
  • Space complexity: O(n)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Top-Down Recursive DFSO(2^n)O(n)Exhaustive branching down to base row.Overlapping subproblems
2.Memoized DPO(n^2)O(n^2)Cache subproblem answers for (r, c).Table allocation
3.Bottom-Up 1D DPOptimalO(n^2)O(n)Iteratively collapse rows upwards into a single 1D array.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Running the inner loop c past r when working bottom-up.

Pitfall 2:

Using top-down and forgetting to find the minimum of the entire last row.

Crucial Edge Cases to Validate:

  • Single row triangle: triangle = [[val]]; returns val.
  • Negative numbers: Handled correctly without modification.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Highlight the elegance of going bottom-up: explaining why bottom-up eliminates boundary conditions and multiple destination comparisons demonstrates strong algorithmic maturity.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is bottom-up DP structurally cleaner than top-down DP for the Triangle problem?

Back to DSA Sheet