Triangle

Medium
321.

Triangle

Triangle is a medium coding problem on arrays and dynamic programming, asked in Amazon, Google, Adobe and Bloomberg interviews.

Given a triangle array, return the minimum path sum from top to bottom.

At each step you may move to an adjacent number on the row below: from index i on the current row you may move to index i or i + 1 on the next.

Example 1

Input
triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output
11
Explanation
The path 2 → 3 → 5 → 1 sums to 11.

Example 2

Input
triangle = [[-10]]
Output
-10

Example 3

Input
triangle = [[1],[2,3]]
Output
3

Constraints

  • 1 <= triangle.length <= 8
  • triangle[i].length == i + 1
  • -100 <= triangle[i][j] <= 100

Follow-up: Can you do it using only O(n) extra space, where n is the number of rows?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function(triangle) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Triangle — Solution in Python, Java & C++

Triangle solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon and Google.

Triangle is a medium coding problem on arrays and dynamic programming, asked in Amazon, Google, Adobe and Bloomberg interviews.

Problem statement

Given a triangle array, return the minimum path sum from top to bottom.

At each step you may move to an adjacent number on the row below: from index i on the current row you may move to index i or i + 1 on the next.

Example 1

Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: The path 2 → 3 → 5 → 1 sums to 11.

Example 2

Input: triangle = [[-10]]
Output: -10

Example 3

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

Constraints

  • 1 <= triangle.length <= 8
  • triangle[i].length == i + 1
  • -100 <= triangle[i][j] <= 100

Follow-up: Can you do it using only O(n) extra space, where n is the number of rows?

Hints for Triangle

  1. Hint 1

    Working top-down forces you to track every partial path; working bottom-up collapses them.

  2. Hint 2

    Start with the last row as the answer for each of its cells, then fold each row above into it.

  3. Hint 3

    One array the width of the base is enough, overwritten in place from left to right.

How to solve Triangle

Fold bottom-up: start with the last row as the answer for its cells, and for each row above set dp[c] = triangle[r][c] + min(dp[c], dp[c+1]).

Approach

  1. Copy the last row into dp.
  2. For r from the second-last row up to 0, update dp[c] for c in 0..r.
  3. Return dp[0].

Why it works

From cell (r, c) the path continues to (r+1, c) or (r+1, c+1), so the best cost from that cell downward is its value plus the better of the two below. Bottom-up leaves the answer at the apex with one array.

Complexity

  • Time — O(n²)
  • Space — O(n)

Pitfalls

  • Top-down needs care at the row edges; bottom-up has no edge cases.

Reference solution

Python

def minimumTotal(triangle) -> int:
    dp = list(triangle[-1])
    for r in range(len(triangle) - 2, -1, -1):
        for c in range(r + 1):
            dp[c] = triangle[r][c] + min(dp[c], dp[c + 1])
    return dp[0]

Java

public static int minimumTotal(int[][] triangle) {
    int n = triangle.length;
    int[] dp = Arrays.copyOf(triangle[n - 1], n);
    for (int r = n - 2; r >= 0; r--) {
        for (int c = 0; c <= r; c++) {
            dp[c] = triangle[r][c] + Math.min(dp[c], dp[c + 1]);
        }
    }
    return dp[0];
}

C++

int minimumTotal(vector<vector<int>>& triangle) {
    int n = (int) triangle.size();
    vector<int> dp = triangle[n - 1];
    for (int r = n - 2; r >= 0; r--) {
        for (int c = 0; c <= r; c++) {
            dp[c] = triangle[r][c] + min(dp[c], dp[c + 1]);
        }
    }
    return dp[0];
}

JavaScript

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

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming