{x}
blog image

Triangle

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
  • -104 <= triangle[i][j] <= 104

 

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

120. Triangle

Problem Description

Given a triangle array, find the minimum path sum from top to bottom. At each step, you can move to an adjacent number in the row below.

Solution Explanation

This problem can be efficiently solved using dynamic programming. The core idea is to build a solution from the bottom up.

Approach:

  1. Initialization: We can either create a separate DP table or, for space optimization, directly modify the input triangle array. The approach using the input array is shown below, offering O(1) space complexity.

  2. Iteration: We iterate through the triangle from the second to last row upwards. For each element triangle[i][j], we add the minimum of its two adjacent elements in the row below (triangle[i+1][j] and triangle[i+1][j+1]). This represents the minimum path sum from that element to the bottom of the triangle.

  3. Result: After iterating through all rows, triangle[0][0] will contain the minimum total path sum from the top to the bottom.

Time and Space Complexity:

  • Time Complexity: O(n^2), where n is the number of rows in the triangle. This is because we iterate through the triangle once.
  • Space Complexity: O(1) (In-place modification of the input triangle). If we used a separate DP table, the space complexity would be O(n^2).

Code in Multiple Languages

Python

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        n = len(triangle)
        for i in range(n - 2, -1, -1):
            for j in range(i + 1):
                triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1])
        return triangle[0][0]

Java

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        for (int i = triangle.size() - 2; i >= 0; --i) {
            for (int j = 0; j <= i; ++j) {
                triangle.get(i).set(j, triangle.get(i).get(j) + Math.min(triangle.get(i + 1).get(j), triangle.get(i + 1).get(j + 1)));
            }
        }
        return triangle.get(0).get(0);
    }
}

C++

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

JavaScript

/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function(triangle) {
    for (let i = triangle.length - 2; i >= 0; i--) {
        for (let j = 0; j <= i; j++) {
            triangle[i][j] += Math.min(triangle[i + 1][j], triangle[i + 1][j + 1]);
        }
    }
    return triangle[0][0];
};

Go

func minimumTotal(triangle [][]int) int {
    for i := len(triangle) - 2; i >= 0; i-- {
        for j := 0; j <= i; j++ {
            triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1])
        }
    }
    return triangle[0][0]
}
 
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

These solutions all follow the same dynamic programming approach, differing only in syntax. The in-place modification optimizes space complexity, making them highly efficient.