Solution: Triangle

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

---

Leetcode Problem #120 (Medium): Triangle

---

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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.

---

Examples:

Example 1:
Input:	triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output:	11
Explanation:	The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined below).
Visual:

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^4 <= triangle[i][j] <= 10^4

---

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

In order to find the best path from the top of the input triangle array (T) to the bottom, we should be able to find the best path to any intermediate spot along that path, as well. That should immediately bring to mind a dynamic programming (DP) solution, as we can divide this solution up into smaller pieces and then build those up to our eventual solution.

The naive idea here might be to do a bottom-up DP approach (which is actually from the start of the path, or the top of T, to the end of the path, or the bottom of T), since that reflects the normal path progression and branching. If we do this, however, we'll need to write extra code to avoid going out-of-bounds when checking the previously completed rows of the DP array. We'll also have to then check the entire bottom row of our DP array to find the best value.

If we use a top-down DP approach (visually bottom to top of T), however, we can avoid having to check for out-of-bounds conditions, as we'll be going from larger rows to smaller rows. Also, we won't need to search for the best solution, because it will automatically be isolated in T[0][0].

Furthermore, since we'll never need to backtrack to previous rows, we can use T as its own in-place DP array, updating the values as we go, in order to achieve a space complexity of O(1) extra space.

In order to accomplish this, we'll just need to iterate backwards through the rows, starting from the second to the last, and figure out what the best path to the bottom would be from each location in the row. Since the values in the row below will already represent the best path from that point, we can just add the lower of the two possible branches to the current location (T[i][j]) at each iteration.

Once we're done, we can simply return T[0][0].

---

Implementation:

For Java, using an in-place DP approach, while saving on space complexity, is less performant than using an O(N) DP array.

---

Javascript Code:

(Jump to: Problem Description || Solution Idea)

var minimumTotal = function(T) {
    for (let i = T.length - 2; ~i; i--) 
        for (let j = T[i].length - 1; ~j; j--) 
            T[i][j] += Math.min(T[i+1][j], T[i+1][j+1])
    return T[0][0]
}

---

Python Code:

(Jump to: Problem Description || Solution Idea)

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

---

Java Code:

(Jump to: Problem Description || Solution Idea)

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

---

C++ Code:

(Jump to: Problem Description || Solution Idea)

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