120. Triangle - Solution & Explanation

Q: Is Triangle easy or hard?

Triangle is generally classified as a medium-level problem. The main difficulty is identifying the dynamic programming recurrence and recognizing that each cell depends only on two cells in the next row.

Q: Triangle Python/Java solution

Triangle solutions in Python or Java usually implement bottom-up dynamic programming. Starting from the last row, maintain a DP array and update each position with triangle[row][col] + min(dp[col], dp[col+1]). This produces the minimum path sum at dp[0] after processing all rows.

Q: How to solve Triangle in O(n)?

Triangle cannot be solved in O(n) time because you must inspect every element in the triangle to determine the minimum path. The best achievable time complexity is O(n^2). However, the space complexity can be reduced to O(n) using a bottom-up DP array.

Q: What is the best approach for Triangle?

The best approach is bottom-up dynamic programming with space optimization. Start from the last row and iteratively compute the minimum path sum for the row above using a 1D array. Each update uses min(dp[i], dp[i+1]) from the row below. This runs in O(n^2) time and O(n) space.

Q: Is Triangle asked at Google/Amazon/Meta?

Triangle is a classic dynamic programming problem frequently used in technical interviews. Variants of this problem have appeared in interviews at companies like Amazon, Google, and Meta because it tests DP state transitions, recursion, and space optimization.

Q: What data structure is used in Triangle?

The input is a triangular array structure, and the main technique uses dynamic programming. Solutions typically use either a 2D DP table or a 1D array for space-optimized bottom-up computation.

Q: What is the time complexity of Triangle?

The optimal dynamic programming solutions run in O(n^2) time because every element in the triangle is processed exactly once. If the triangle has n rows, it contains about n^2/2 elements. Both top-down memoization and bottom-up DP share this same time complexity.

The problem

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 <= 200
triangle[0].length == 1
triangle[i].length == triangle[i - 1].length + 1
-10⁴ <= triangle[i][j] <= 10⁴

Follow up: Could you do this using only O(n) extra space, where n is the total number of rows in the triangle?

Approach overview

Problem Overview: You are given a triangular array where each row has one more element than the previous row. Starting at the top, move to adjacent numbers in the row directly below and compute the minimum possible path sum from top to bottom.

Approach 1: Top-Down Dynamic Programming with Memoization (Time: O(n^2), Space: O(n^2))

This approach treats the triangle as a recursive decision tree. From position (row, col), you can move to (row+1, col) or (row+1, col+1). Use recursion to compute the minimum path sum from the current cell to the bottom, and store results in a memo table so each subproblem is solved once. Memoization eliminates repeated work that appears in naive recursion. This approach is intuitive if you naturally think about exploring paths top‑down and caching results.

Approach 2: Bottom-Up Dynamic Programming (2D DP) (Time: O(n^2), Space: O(n^2))

Instead of exploring paths recursively, build the solution from the bottom row upward. Create a DP table where dp[row][col] stores the minimum path sum from that position to the bottom. For each cell, compute triangle[row][col] + min(dp[row+1][col], dp[row+1][col+1]). Because each value depends only on the row below, iterating from the second-last row to the top fills the table efficiently. This converts the recursive idea into a clean iterative dynamic programming solution.

Approach 3: Bottom-Up Dynamic Programming (Space Optimized) (Time: O(n^2), Space: O(n))

The DP transition only depends on the next row, so a full 2D table is unnecessary. Copy the last row into a 1D array and update it while moving upward through the triangle. For each element, update dp[col] = triangle[row][col] + min(dp[col], dp[col+1]). The array always represents the minimum path sums for the row below the current one. This keeps the same time complexity while reducing memory usage to linear space. The triangle itself is just an array structure, while the optimization relies on recognizing overlapping subproblems typical in dynamic programming.

Recommended for interviews: The bottom-up dynamic programming solution with 1D optimization is what interviewers usually expect. It demonstrates that you understand DP transitions and space optimization. Explaining the top-down memoization version first can help show how you derived the recurrence before converting it into the optimal iterative form.

Approach 1: Dynamic Programming Bottom-Up Approach

In this approach, we'll use dynamic programming (DP) to achieve the solution. We'll start from the bottom of the triangle and minimize the sum path to the top. We'll keep updating the path sum in a DP array as we move to the top row.

Python

def minimumTotal(triangle):
    dp = triangle[-1]
    for row in range(len(triangle) - 2, -1, -1):
        for col in range(len(triangle[row])):
            dp[col] = triangle[row][col] + min(dp[col], dp[col + 1])
    return dp[0]

triangle = [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]
print(minimumTotal(triangle))

Java

import java.util.List;

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

    public static void main(String[] args) {
        Solution sol = new Solution();
        List<List<Integer>> triangle = List.of(
            List.of(2), List.of(3, 4), List.of(6, 5, 7), List.of(4, 1, 8, 3)
        );
        System.out.println(sol.minimumTotal(triangle));
    }
}

C++

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        vector<int> dp(triangle.back());
        for (int row = triangle.size() - 2; row >= 0; --row) {
            for (int col = 0; col < triangle[row].size(); ++col) {
                dp[col] = triangle[row][col] + min(dp[col], dp[col + 1]);
            }
        }
        return dp[0];
    }
};

int main() {
    Solution sol;
    vector<vector<int>> triangle = {{2}, {3, 4}, {6, 5, 7}, {4, 1, 8, 3}};
    cout << sol.minimumTotal(triangle) << endl;
    return 0;
}

JavaScript

var minimumTotal = function(triangle) {
    let dp = triangle[triangle.length - 1];
    for (let row = triangle.length - 2; row >= 0; row--) {
        for (let col = 0; col < triangle[row].length; col++) {
            dp[col] = triangle[row][col] + Math.min(dp[col], dp[col + 1]);
        }
    }
    return dp[0];
};

console.log(minimumTotal([[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]));

#include <stdio.h>
#include <limits.h>

int minimumTotal(int** triangle, int triangleSize, int* triangleColSize) {
    int dp[triangleSize];
    for (int i = 0; i < triangleColSize[triangleSize - 1]; ++i) {
        dp[i] = triangle[triangleSize - 1][i];
    }
    
    for (int row = triangleSize - 2; row >= 0; --row) {
        for (int col = 0; col < triangleColSize[row]; ++col) {
            dp[col] = triangle[row][col] + (dp[col] < dp[col + 1] ? dp[col] : dp[col + 1]);
        }
    }
    return dp[0];
}

int main() {
    int t1[] = {2};
    int t2[] = {3, 4};
    int t3[] = {6, 5, 7};
    int t4[] = {4, 1, 8, 3};

    int* triangle[] = {t1, t2, t3, t4};
    int columnSize[] = {1, 2, 3, 4};

    int result = minimumTotal(triangle, 4, columnSize);
    printf("%d\n", result);

    return 0;
}

using System;
using System.Collections.Generic;

public class Solution {
    public int MinimumTotal(IList<IList<int>> triangle) {
        int[] dp = new int[triangle.Count];
        for (int i = 0; i < triangle[^1].Count; i++) {
            dp[i] = triangle[^1][i];
        }
        for (int row = triangle.Count - 2; row >= 0; row--) {
            for (int col = 0; col < triangle[row].Count; col++) {
                dp[col] = triangle[row][col] + Math.Min(dp[col], dp[col + 1]);
            }
        }
        return dp[0];
    }

    public static void Main() {
        var solution = new Solution();
        var triangle = new List<IList<int>> {
            new List<int> {2},
            new List<int> {3, 4},
            new List<int> {6, 5, 7},
            new List<int> {4, 1, 8, 3}
        };
        Console.WriteLine(solution.MinimumTotal(triangle));
    }
}

The Python function minimumTotal utilizes dynamic programming to track the minimum path sum from bottom to top. The input triangle gets updated iteratively via the variable dp which represents the current base row in the triangle.

Complexity

Time Complexity: O(n^2)
Space Complexity: O(n) (although it mutates the input to prevent additional space usage)

Try this approach in the editor

Approach 2: Top-Down Dynamic Programming with Memoization

This approach uses a top-down strategy with memoization to store already computed results, avoiding redundant calculations. Each recursive call stores the minimum path sum starting from the current index down to the base of the triangle.

Python

def minimumTotal(triangle):
    memo = [[None] * len(row) for row in triangle]

    def dfs(row, col):
        if row == len(triangle):
            return 0
        if memo[row][col] is not None:
            return memo[row][col]

        left = dfs(row + 1, col)
        right = dfs(row + 1, col + 1)
        memo[row][col] = triangle[row][col] + min(left, right)
        return memo[row][col]

    return dfs(0, 0)

triangle = [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]
print(minimumTotal(triangle))

Java

import java.util.List;

class Solution {
    Integer[][] memo;

    public int dfs(int row, int col, List<List<Integer>> triangle) {
        if (row == triangle.size()) return 0;
        if (memo[row][col] != null) return memo[row][col];

        int left = dfs(row + 1, col, triangle);
        int right = dfs(row + 1, col + 1, triangle);
        memo[row][col] = triangle.get(row).get(col) + Math.min(left, right);
        return memo[row][col];
    }

    public int minimumTotal(List<List<Integer>> triangle) {
        memo = new Integer[triangle.size()][triangle.size()];
        return dfs(0, 0, triangle);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        List<List<Integer>> triangle = List.of(
            List.of(2), List.of(3, 4), List.of(6, 5, 7), List.of(4, 1, 8, 3)
        );
        System.out.println(sol.minimumTotal(triangle));
    }
}

C++

#include <vector>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;

int memo[201][201];

class Solution {
public:
    int dfs(int row, int col, vector<vector<int>>& triangle) {
        if (row == triangle.size()) return 0;
        if (memo[row][col] != -1) return memo[row][col];

        int left = dfs(row + 1, col, triangle);
        int right = dfs(row + 1, col + 1, triangle);
        memo[row][col] = triangle[row][col] + min(left, right);
        return memo[row][col];
    }

    int minimumTotal(vector<vector<int>>& triangle) {
        memset(memo, -1, sizeof(memo));
        return dfs(0, 0, triangle);
    }
};

int main() {
    Solution sol;
    vector<vector<int>> triangle = {{2}, {3, 4}, {6, 5, 7}, {4, 1, 8, 3}};
    cout << sol.minimumTotal(triangle) << endl;
    return 0;
}

JavaScript

var minimumTotal = function(triangle) {
    const memo = new Array(triangle.length).fill().map(() => Array(triangle.length).fill(null));
    
    const dfs = (row, col) => {
        if (row === triangle.length) return 0;
        if (memo[row][col] !== null) return memo[row][col];
        const left = dfs(row + 1, col);
        const right = dfs(row + 1, col + 1);
        memo[row][col] = triangle[row][col] + Math.min(left, right);
        return memo[row][col];
    };
    return dfs(0, 0);
};

console.log(minimumTotal([[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]));

#include <stdio.h>
#include <string.h>

#define MAX 201
int memo[MAX][MAX];

int dfs(int row, int col, int** triangle, int triangleSize, int* triangleColSize) {
    if (row == triangleSize) return 0;
    if (memo[row][col] != -1) return memo[row][col];
    int left = dfs(row + 1, col, triangle, triangleSize, triangleColSize);
    int right = dfs(row + 1, col + 1, triangle, triangleSize, triangleColSize);
    memo[row][col] = triangle[row][col] + (left < right ? left : right);
    return memo[row][col];
}

int minimumTotal(int** triangle, int triangleSize, int* triangleColSize) {
    memset(memo, -1, sizeof(memo));
    return dfs(0, 0, triangle, triangleSize, triangleColSize);
}

int main() {
    int t1[] = {2};
    int t2[] = {3, 4};
    int t3[] = {6, 5, 7};
    int t4[] = {4, 1, 8, 3};

    int* triangle[] = {t1, t2, t3, t4};
    int columnSize[] = {1, 2, 3, 4};

    int result = minimumTotal(triangle, 4, columnSize);
    printf("%d\n", result);

    return 0;
}

using System;
using System.Collections.Generic;

public class Solution {
    private int?[,] memo;

    public int MinimumTotal(IList<IList<int>> triangle) {
        memo = new int?[triangle.Count, triangle.Count];
        return Dfs(0, 0, triangle);
    }

    private int Dfs(int row, int col, IList<IList<int>> triangle) {
        if (row == triangle.Count) return 0;

        if (memo[row, col].HasValue) return memo[row, col].Value;

        int left = Dfs(row + 1, col, triangle);
        int right = Dfs(row + 1, col + 1, triangle);

        memo[row, col] = triangle[row][col] + Math.Min(left, right);
        return memo[row, col].Value;
    }

    public static void Main() {
        var solution = new Solution();
        var triangle = new List<IList<int>> {
            new List<int> {2},
            new List<int> {3, 4},
            new List<int> {6, 5, 7},
            new List<int> {4, 1, 8, 3}
        };
        Console.WriteLine(solution.MinimumTotal(triangle));
    }
}

Python's iterative function utilizes a multi-layered array memo, storing inter-path computations to enhance speed. The primary recursive dfs function checks memo for known results prior to recursive descent.

Complexity

Time Complexity: O(n^2)
Space Complexity: O(n^2)

Try this approach in the editor

Approach 3: Dynamic Programming

We define f[i][j] as the minimum path sum from the bottom of the triangle to position (i, j). Here, position (i, j) refers to the position in row i and column j of the triangle (both indexed from 0). We have the following state transition equation:

$f[i][j] = min(f[i + 1][j], f[i + 1][j + 1]) + triangle[i][j]

The answer is f[0][0]$.

TypeScript

function minimumTotal(triangle: number[][]): number {
    const n = triangle.length;
    const f: number[][] = Array.from({ length: n + 1 }, () => Array(n + 1).fill(0));
    for (let i = n - 1; i >= 0; --i) {
        for (let j = 0; j <= i; ++j) {
            f[i][j] = Math.min(f[i + 1][j], f[i + 1][j + 1]) + triangle[i][j];
        }
    }
    return f[0][0];
}

func minimumTotal(triangle [][]int) int {
	n := len(triangle)
	f := make([][]int, n+1)
	for i := range f {
		f[i] = make([]int, n+1)
	}
	for i := n - 1; i >= 0; i-- {
		for j := 0; j <= i; j++ {
			f[i][j] = min(f[i+1][j], f[i+1][j+1]) + triangle[i][j]
		}
	}
	return f[0][0]
}

Rust

impl Solution {
    pub fn minimum_total(triangle: Vec<Vec<i32>>) -> i32 {
        let n = triangle.len();
        let mut f = vec![vec![0; n + 1]; n + 1];
        for i in (0..n).rev() {
            for j in 0..=i {
                f[i][j] = f[i + 1][j].min(f[i + 1][j + 1]) + triangle[i][j];
            }
        }
        f[0][0]
    }
}

Try this approach in the editor

Approach 4: Dynamic Programming (Space Optimization)

We notice that the state f[i][j] only depends on states f[i + 1][j] and f[i + 1][j + 1]. Therefore, we can use a one-dimensional array instead of a two-dimensional array, reducing the space complexity from O(n^2) to O(n).

The time complexity is O(n^2), and the space complexity is O(n), where n is the number of rows in the triangle.

TypeScript

function minimumTotal(triangle: number[][]): number {
    const n = triangle.length;
    const f: number[] = Array(n + 1).fill(0);
    for (let i = n - 1; i >= 0; --i) {
        for (let j = 0; j <= i; ++j) {
            f[j] = Math.min(f[j], f[j + 1]) + triangle[i][j];
        }
    }
    return f[0];
}

func minimumTotal(triangle [][]int) int {
	n := len(triangle)
	f := make([]int, n+1)
	for i := n - 1; i >= 0; i-- {
		for j := 0; j <= i; j++ {
			f[j] = min(f[j], f[j+1]) + triangle[i][j]
		}
	}
	return f[0]
}

Rust

impl Solution {
    pub fn minimum_total(triangle: Vec<Vec<i32>>) -> i32 {
        let n = triangle.len();
        let mut f = vec![0; n + 1];
        for i in (0..n).rev() {
            for j in 0..=i {
                f[j] = f[j].min(f[j + 1]) + triangle[i][j];
            }
        }
        f[0]
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Dynamic Programming Bottom-Up Approach	Time Complexity: `O(n^2)` Space Complexity: `O(n)` (although it mutates the input to prevent additional space usage)
Top-Down Dynamic Programming with Memoization	Time Complexity: `O(n^2)` Space Complexity: `O(n^2)`
Dynamic Programming	–
Dynamic Programming (Space Optimization)	–

Complexity analysis

Approach	Time	Space	When to Use
Top-Down DP with Memoization	O(n^2)	O(n^2)	When reasoning recursively about paths and caching overlapping subproblems
Bottom-Up DP (2D table)	O(n^2)	O(n^2)	Clear iterative implementation that mirrors the DP recurrence
Bottom-Up DP (1D optimized)	O(n^2)	O(n)	Preferred approach when minimizing extra memory in interviews

Frequently asked questions

Is Triangle easy or hard?

Triangle is generally classified as a medium-level problem. The main difficulty is identifying the dynamic programming recurrence and recognizing that each cell depends only on two cells in the next row.

Triangle Python/Java solution

Triangle solutions in Python or Java usually implement bottom-up dynamic programming. Starting from the last row, maintain a DP array and update each position with triangle[row][col] + min(dp[col], dp[col+1]). This produces the minimum path sum at dp[0] after processing all rows.

How to solve Triangle in O(n)?

Triangle cannot be solved in O(n) time because you must inspect every element in the triangle to determine the minimum path. The best achievable time complexity is O(n^2). However, the space complexity can be reduced to O(n) using a bottom-up DP array.

What is the best approach for Triangle?

The best approach is bottom-up dynamic programming with space optimization. Start from the last row and iteratively compute the minimum path sum for the row above using a 1D array. Each update uses min(dp[i], dp[i+1]) from the row below. This runs in O(n^2) time and O(n) space.

Is Triangle asked at Google/Amazon/Meta?

Triangle is a classic dynamic programming problem frequently used in technical interviews. Variants of this problem have appeared in interviews at companies like Amazon, Google, and Meta because it tests DP state transitions, recursion, and space optimization.

What data structure is used in Triangle?

The input is a triangular array structure, and the main technique uses dynamic programming. Solutions typically use either a 2D DP table or a 1D array for space-optimized bottom-up computation.

What is the time complexity of Triangle?

The optimal dynamic programming solutions run in O(n^2) time because every element in the triangle is processed exactly once. If the triangle has n rows, it contains about n^2/2 elements. Both top-down memoization and bottom-up DP share this same time complexity.

Triangle solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming Bottom-Up Approach

Approach 2: Top-Down Dynamic Programming with Memoization

Approach 3: Dynamic Programming

Approach 4: Dynamic Programming (Space Optimization)

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Triangle solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming Bottom-Up Approach

Approach 2: Top-Down Dynamic Programming with Memoization

Approach 3: Dynamic Programming

Approach 4: Dynamic Programming (Space Optimization)

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems