LeetCode 120. Triangle (javascript solution)

Description:

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.

Solution:

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

var minimumTotal = function(triangle) {
    // Start from the 2nd to the bottom of the triangle
    for (let i = triangle.length-2; i >= 0; i--)
        // Add previous row cells to current cells and set the sum that is the smallest
        for (let j = 0; j < triangle[i].length; j++)
            triangle[i][j] += Math.min(triangle[i+1][j], triangle[i+1][j+1])
    // The cell at the top of the triangle will be the smallest sum of the path that goes from the bottom to the top
    return triangle[0][0]
}

Blog

LeetCode 120. Triangle (javascript solution)

codingpineapple

Description:

Solution:

Join Our Newsletter. No Spam, Only the good stuff.

Related