Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Triangle

MEDIUMProblemSolveExternal Links

Description

Given a triangle array (a list of lists where row i has i + 1 elements), return the minimum path sum from the top of the triangle to the bottom.

At each step you may move to an adjacent number in the row below. More precisely, if you are at index i in the current row, you may move to either index i or index i + 1 in the next row. You must start at the single element in row 0 and end at some element in the last row, choosing exactly one element from each row along the way.

A triangle with 4 rows showing values [2], [3,4], [6,5,7], [4,1,8,3]. The minimum path 2→3→5→1 is highlighted in green, summing to 11.
A triangle with 4 rows showing values [2], [3,4], [6,5,7], [4,1,8,3]. The minimum path 2→3→5→1 is highlighted in green, summing to 11.

Examples

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.

Why this path? Starting at 2, we choose 3 (smaller than 4). From 3, we choose 5 (smaller neighbor; going to 6 would add more). From 5, we choose 1 (much smaller than 8). Total: 11.

Example 2

Input: triangle = [[-10]]

Output: -10

Explanation: The triangle has a single element. The only path is just -10 itself.

Example 3

Input: triangle = [[1],[2,3],[1,5,1]]

Output: 4

Explanation: The triangle:

  1
 2 3
1 5 1

All paths: 1→2→1 = 4, 1→2→5 = 8, 1→3→5 = 9, 1→3→1 = 5. The minimum is 4 (path 1→2→1). Note that greedily choosing the smallest at each step (1→2→1 = 4) happens to work here, but greedy is not always correct for this problem.

Constraints

  • 1 ≤ triangle.length ≤ 200
  • triangle[0].length == 1
  • triangle[i].length == triangle[i - 1].length + 1
  • -10^4 ≤ triangle[i][j] ≤ 10^4

Editorial

Brute Force

Intuition

The most straightforward approach is to explore every possible path from the top to the bottom and find the one with the smallest sum.

Imagine standing at the peak of a mountain with branching trails going down. At each junction, you can go left or right. To find the shortest trail, you could walk every single trail, note its length, and pick the shortest one.

We implement this with recursion: from any position (row, col), we try both children (row+1, col) and (row+1, col+1), take the minimum of their path sums, and add the current cell's value. The base case is reaching the row below the last row, where we return 0.

Step-by-Step Explanation

Let's trace through with triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] (Example 1):

Triangle:

   2        ← row 0
  3 4       ← row 1
 6 5 7      ← row 2
4 1 8 3     ← row 3

Step 1: Call f(0,0). Value = 2. We need min(f(1,0), f(1,1)). Explore f(1,0) first.
State: path = [2], row = 0, col = 0.

Step 2: Call f(1,0). Value = 3. Need min(f(2,0), f(2,1)). Explore f(2,0).
State: path = [2, 3], running_sum = 5.

Step 3: Call f(2,0). Value = 6. Need min(f(3,0), f(3,1)). Explore f(3,0).
State: path = [2, 3, 6], running_sum = 11.

Step 4: f(3,0) = 4 (bottom row). Path 2→3→6→4 = 15.
f(3,1) = 1 (bottom row). Path 2→3→6→1 = 12.
f(2,0) = 6 + min(4, 1) = 6 + 1 = 7. ✓ Computed.

Step 5: Call f(2,1). Value = 5. Need min(f(3,1), f(3,2)).
f(3,1) = 1, f(3,2) = 8.
f(2,1) = 5 + min(1, 8) = 5 + 1 = 6. ✓ Computed.

Step 6: f(1,0) = 3 + min(f(2,0), f(2,1)) = 3 + min(7, 6) = 3 + 6 = 9. ✓ Computed.

Step 7: Now explore f(1,1). Value = 4. Need min(f(2,1), f(2,2)).
⚠️ f(2,1) was already computed in Step 5 = 6. But without memoization, we recompute it!
f(2,1) recomputed: 5 + min(1, 8) = 6. Same result, wasted work.
f(2,2) = 7 + min(f(3,2), f(3,3)) = 7 + min(8, 3) = 7 + 3 = 10.
f(1,1) = 4 + min(6, 10) = 4 + 6 = 10. ✓ Computed.

Step 8: f(0,0) = 2 + min(f(1,0), f(1,1)) = 2 + min(9, 10) = 2 + 9 = 11.

Result: Minimum path sum = 11.

Key observation: f(2,1) was computed twice, and f(3,1) and f(3,2) were each computed twice. In a triangle with n rows, the number of distinct subproblems is only n(n+1)/2, but the brute force explores 2^(n-1) paths — exponentially more. This redundancy is the hallmark of overlapping subproblems, perfectly suited for dynamic programming.

Algorithm

  1. Define a recursive function dfs(row, col) that returns the minimum path sum starting from position (row, col) to the bottom.
  2. Base case: If row == n (past the last row), return 0.
  3. Recursive case: Return triangle[row][col] + min(dfs(row+1, col), dfs(row+1, col+1)).
  4. Call dfs(0, 0) and return the result.

Code

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

class Solution {
public:
    int dfs(vector<vector<int>>& triangle, int row, int col, int n) {
        if (row == n) return 0;
        return triangle[row][col] + min(
            dfs(triangle, row + 1, col, n),
            dfs(triangle, row + 1, col + 1, n)
        );
    }
    
    int minimumTotal(vector<vector<int>>& triangle) {
        return dfs(triangle, 0, 0, triangle.size());
    }
};
class Solution:
    def minimumTotal(self, triangle: list[list[int]]) -> int:
        n = len(triangle)
        
        def dfs(row: int, col: int) -> int:
            if row == n:
                return 0
            return triangle[row][col] + min(
                dfs(row + 1, col),
                dfs(row + 1, col + 1)
            )
        
        return dfs(0, 0)
import java.util.*;

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        return dfs(triangle, 0, 0, triangle.size());
    }
    
    private int dfs(List<List<Integer>> triangle, int row, int col, int n) {
        if (row == n) return 0;
        return triangle.get(row).get(col) + Math.min(
            dfs(triangle, row + 1, col, n),
            dfs(triangle, row + 1, col + 1, n)
        );
    }
}

Complexity Analysis

Time Complexity: O(2^n)

At each cell, we branch into two recursive calls (left child and right child). With n rows, the recursion tree has depth n and up to 2^(n-1) leaves — one for each path from top to bottom. For n = 200, this is 2^199 ≈ 10^60 operations, which is astronomically beyond any computer's capability.

Space Complexity: O(n)

The recursion stack goes at most n levels deep (one level per row). No additional data structures are used.

Why This Approach Is Not Efficient

The brute force explores 2^(n-1) paths, but the triangle only contains n(n+1)/2 distinct cells. Many cells lie on multiple paths — for example, the middle cell of a row is reached from two parents above it. The brute force recomputes the minimum path sum from each such cell every time it's visited, leading to massive redundancy.

For a triangle with 200 rows, the number of distinct subproblems is only 200 × 201 / 2 = 20,100, but the brute force explores ~10^60 paths. The ratio of wasted to useful work is astronomical.

Key insight: Since the minimum path sum from any cell (row, col) depends only on the cell itself and the subproblems below it (not on how we arrived at that cell), we have optimal substructure and overlapping subproblems — the two hallmarks of dynamic programming. By caching each cell's result after the first computation, we can reduce the time from O(2^n) to O(n²).

Better Approach - Memoization (Top-Down DP)

Intuition

Memoization is the simplest upgrade from brute force: keep the exact same recursive structure, but add a cache (memo table) that stores the result for each cell after computing it the first time. When the recursion revisits a cell, we return the cached value instantly instead of recomputing the entire subtree below it.

Think of it as leaving breadcrumbs on the mountain trails. The first time you walk a section of trail and measure its cost, you write the cost on a sign. If you later reach the same junction from a different route, you just read the sign instead of walking the trail again.

The memo table mirrors the triangle's shape: memo[row][col] stores the minimum path sum from (row, col) to the bottom. Initially all entries are unset. As the recursion returns values, it fills the table bottom-up. Future lookups hit the cache in O(1).

Step-by-Step Explanation

Let's trace through with triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] (Example 1):

Memo table starts as all unfilled (null). As recursion returns, we fill cells.

Step 1: DFS reaches the bottom row. f(3,0)=4, f(3,1)=1. Memo row 3 partially filled: [4, 1, -, -].

Step 2: f(2,0) = 6 + min(memo[3][0], memo[3][1]) = 6 + min(4, 1) = 7. Memo[2][0] = 7.

Step 3: f(3,1) = 1 (CACHE HIT — already computed!). f(3,2) = 8 (new base case). Memo row 3: [4, 1, 8, -].

Step 4: f(2,1) = 5 + min(memo[3][1], memo[3][2]) = 5 + min(1, 8) = 6. Memo[2][1] = 6.

Step 5: f(1,0) = 3 + min(memo[2][0], memo[2][1]) = 3 + min(7, 6) = 9. Memo[1][0] = 9.

Step 6: f(2,1) = 6 (CACHE HIT!). f(3,2) = 8 (CACHE HIT!). f(3,3) = 3. Memo row 3: [4, 1, 8, 3].

Step 7: f(2,2) = 7 + min(memo[3][2], memo[3][3]) = 7 + min(8, 3) = 10. Memo[2][2] = 10.

Step 8: f(1,1) = 4 + min(memo[2][1], memo[2][2]) = 4 + min(6, 10) = 10. Memo[1][1] = 10.

Step 9: f(0,0) = 2 + min(memo[1][0], memo[1][1]) = 2 + min(9, 10) = 11. Memo[0][0] = 11.

Result: Minimum path sum = 11. Three cache hits saved us from recomputing 3 subtrees.

Memoization — Filling the Cache as Recursion Returns — Watch the memo table fill from bottom to top as the DFS recursion computes and caches each cell's minimum path sum. Cache hits are highlighted when a previously computed cell is reused.

Algorithm

  1. Create a memo table matching the triangle's dimensions, initialized to a sentinel value (e.g., INT_MAX or null).
  2. Define dfs(row, col):
    • If row == n: return 0 (past bottom).
    • If memo[row][col] is already computed: return it (cache hit).
    • Otherwise: compute triangle[row][col] + min(dfs(row+1, col), dfs(row+1, col+1)), store in memo[row][col], and return it.
  3. Return dfs(0, 0).

Code

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

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        vector<vector<int>> memo(n, vector<int>(n, INT_MAX));
        return dfs(triangle, 0, 0, n, memo);
    }
    
    int dfs(vector<vector<int>>& triangle, int row, int col, int n,
            vector<vector<int>>& memo) {
        if (row == n) return 0;
        if (memo[row][col] != INT_MAX) return memo[row][col];
        memo[row][col] = triangle[row][col] + min(
            dfs(triangle, row + 1, col, n, memo),
            dfs(triangle, row + 1, col + 1, n, memo)
        );
        return memo[row][col];
    }
};
class Solution:
    def minimumTotal(self, triangle: list[list[int]]) -> int:
        n = len(triangle)
        memo = {}
        
        def dfs(row: int, col: int) -> int:
            if row == n:
                return 0
            if (row, col) in memo:
                return memo[(row, col)]
            memo[(row, col)] = triangle[row][col] + min(
                dfs(row + 1, col),
                dfs(row + 1, col + 1)
            )
            return memo[(row, col)]
        
        return dfs(0, 0)
import java.util.*;

class Solution {
    private int[][] memo;
    
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        memo = new int[n][n];
        for (int[] row : memo) Arrays.fill(row, Integer.MAX_VALUE);
        return dfs(triangle, 0, 0, n);
    }
    
    private int dfs(List<List<Integer>> triangle, int row, int col, int n) {
        if (row == n) return 0;
        if (memo[row][col] != Integer.MAX_VALUE) return memo[row][col];
        memo[row][col] = triangle.get(row).get(col) + Math.min(
            dfs(triangle, row + 1, col, n),
            dfs(triangle, row + 1, col + 1, n)
        );
        return memo[row][col];
    }
}

Complexity Analysis

Time Complexity: O(n²)

There are n(n+1)/2 distinct cells in the triangle (1 + 2 + ... + n). Each cell is computed exactly once and cached. Each computation does O(1) work (one addition, one min). Total: O(n²).

For n = 200: 200 × 201 / 2 = 20,100 operations. Extremely fast.

Space Complexity: O(n²)

The memo table stores one value per triangle cell: n(n+1)/2 ≈ O(n²) space. Additionally, the recursion stack uses O(n) space (one frame per row). Total: O(n²).

Why This Approach Is Not Efficient

The memoization approach achieves optimal O(n²) time, but it uses O(n²) extra space for the memo table. The problem's follow-up asks: can we solve this using only O(n) extra space?

The key observation: we don't need to store the entire memo table simultaneously. If we process the triangle bottom-to-top (iteratively, not recursively), then when computing row r, we only need the results from row r+1 — we never look further down. This means we can store just one row of results at a time using a single 1D array of size n.

This leads to the bottom-up DP with space optimization approach: start from the last row, and iteratively collapse the triangle upward, overwriting the same array at each level.

Optimal Approach - Bottom-Up DP (Space Optimized)

Intuition

Instead of working top-down with recursion, we flip the problem and work bottom-up. We start with the last row as our initial DP array, then iterate upward row by row. For each cell in the current row, we update the DP array: dp[col] = triangle[row][col] + min(dp[col], dp[col+1]).

Think of it like water flowing uphill. Imagine each cell at the bottom of the triangle has a certain cost. The cell one row above looks at its two children below, picks the cheaper one, and adds its own cost. This "cheapest path" bubbles up row by row until only one value remains at the top — the answer.

The beauty of this approach:

  • We only ever need the previous row's results (stored in dp), not the entire table.
  • We overwrite dp in-place from left to right. When computing dp[col], the old dp[col] and dp[col+1] are the children's costs from the row below, and they haven't been overwritten yet for this row.
  • After processing all rows, dp[0] holds the minimum path sum from the top.

This satisfies the O(n) space follow-up constraint.

Step-by-Step Explanation

Let's trace through with triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] (Example 1):

Step 1: Initialize dp = copy of last row = [4, 1, 8, 3].

Step 2: Process row 2 (values [6, 5, 7]):

  • dp[0] = 6 + min(dp[0], dp[1]) = 6 + min(4, 1) = 7
  • dp[1] = 5 + min(dp[1], dp[2]) = 5 + min(1, 8) = 6
  • dp[2] = 7 + min(dp[2], dp[3]) = 7 + min(8, 3) = 10
  • dp = [7, 6, 10, 3]

Step 3: Process row 1 (values [3, 4]):

  • dp[0] = 3 + min(dp[0], dp[1]) = 3 + min(7, 6) = 9
  • dp[1] = 4 + min(dp[1], dp[2]) = 4 + min(6, 10) = 10
  • dp = [9, 10, 10, 3]

Step 4: Process row 0 (values [2]):

  • dp[0] = 2 + min(dp[0], dp[1]) = 2 + min(9, 10) = 11
  • dp = [11, 10, 10, 3]

Step 5: Return dp[0] = 11.

The answer bubbled up through the triangle: bottom row [4,1,8,3] → [7,6,10] → [9,10] → [11].

Bottom-Up DP — Collapsing the Triangle into a Single Value — Watch the 1D dp array transform row by row from bottom to top. Each cell picks the minimum of its two children below and adds its own value, until only the answer remains at dp[0].

Algorithm

  1. Initialize dp as a copy of the triangle's last row.
  2. Iterate row from n - 2 down to 0:
    • For each col from 0 to row:
      • dp[col] = triangle[row][col] + min(dp[col], dp[col + 1])
  3. Return dp[0].

Code

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

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        vector<int> dp(triangle[n - 1].begin(), triangle[n - 1].end());
        
        for (int row = n - 2; row >= 0; row--) {
            for (int col = 0; col <= row; col++) {
                dp[col] = triangle[row][col] + min(dp[col], dp[col + 1]);
            }
        }
        
        return dp[0];
    }
};
class Solution:
    def minimumTotal(self, triangle: list[list[int]]) -> int:
        n = len(triangle)
        dp = list(triangle[-1])  # copy of last row
        
        for row in range(n - 2, -1, -1):
            for col in range(row + 1):
                dp[col] = triangle[row][col] + min(dp[col], dp[col + 1])
        
        return dp[0]
import java.util.*;

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = triangle.get(n - 1).get(i);
        }
        
        for (int row = n - 2; row >= 0; row--) {
            for (int col = 0; col <= row; col++) {
                dp[col] = triangle.get(row).get(col) +
                          Math.min(dp[col], dp[col + 1]);
            }
        }
        
        return dp[0];
    }
}

Complexity Analysis

Time Complexity: O(n²)

We process each cell of the triangle exactly once. Row r has r + 1 cells, so the total work is 1 + 2 + ... + n = n(n+1)/2, which is O(n²). Each cell does O(1) work (one min comparison and one addition).

For n = 200: 200 × 201 / 2 = 20,100 operations. Extremely fast.

Space Complexity: O(n)

We use a single 1D array dp of size n (the number of rows, which equals the length of the last row). No recursion stack is needed since we iterate. This satisfies the follow-up constraint of O(n) extra space.

Compared to the memoization approach which uses O(n²) space for the memo table, the bottom-up approach reduces space by a factor of n/2 — from ~20,000 entries to just 200 for a 200-row triangle.