LeetCode 120 — Triangle Minimum Path Sum

What does it solve?

Given a triangle array, find the minimum path sum from top to bottom. At each step you may move to an adjacent number in the row below — meaning from position [r][c] you can go to [r+1][c] or [r+1][c+1].

Bottom-up DP: start from the last row and work upward. At each cell, add the minimum of its two children below. The answer sits at the apex after the sweep.

The core idea

// copy last row into dp[]
dp = triangle[n-1].copy()

for row = n-2 downto 0:
  for col = 0 to row:
    dp[col] = triangle[row][col]
          + min(dp[col], dp[col+1])

return dp[0]

Complexity

Time complexity

O(N²)

We process each cell of the triangle exactly once — there are 1+2+…+N = N(N+1)/2 cells in total.

Space complexity

O(N)

We only keep a single 1-D DP array of size N (the width of the last row). No 2-D table needed.

Examples & edge cases

Live animation — bottom-up DP

Currently computing DP value filled Left child chosen Optimal path node Minimum in last row

Original triangle

DP array (1-D, evolving bottom-up)

Optimal path →

row: — col: — dp[col] = — answer: —

Step — of —

Current row

—

Current col

—

min(child-L, child-R)

—

dp[col] after

—

Select an example and press Play to start.

✓ Answer: —

Speed Medium

Step-by-step table

Step	Phase	Row	Col	triangle[r][c]	child-L (dp[c])	child-R (dp[c+1])	new dp[c]

C++ implementation

triangle_min_path.cpp

#include <bits/stdc++.h>
using namespace std;

int minimumTotal(vector<vector<int>>& triangle) {
    int n = triangle.size();

    // start dp as a copy of the last row
    vector<int> dp = triangle[n - 1];

    // fill upward from second-to-last row
    for (int row = n - 2; row >= 0; row--) {
        for (int col = 0; col <= row; col++) {
            // dp[col] and dp[col+1] are the two children below
            dp[col] = triangle[row][col]
                      + min(dp[col], dp[col + 1]);
        }
    }

    return dp[0];  // apex accumulates the answer
}

int main() {
    vector<vector<int>> triangle = {
        {2},
        {3, 4},
        {6, 5, 7},
        {4, 1, 8, 3}
    };
    cout << minimumTotal(triangle) << "\n";  // 11
    return 0;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars