Skip to content

120. Triangle

https://leetcode.com/problems/triangle/

js
/**
 * @param {number[][]} triangle
 * @return {number}
 */
function minimumTotal(triangle) {
    let prev = []
    let result = triangle[0]

    for (let i = 1; i < triangle.length; i++) {
        prev = result
        result = []
        const row = triangle[i]

        for (let j = 0; j < i + 1; j++) {
            if (j === 0 || (j < i && prev[j - 1] > prev[j])) {
                result.push(prev[j] + row[j])
            } else {
                result.push(prev[j - 1] + row[j])
            }
        }
    }

    return Math.min(...result)
}
py
class Solution(object):

    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        prev, result = [], triangle[0]

        for i in range(1, len(triangle)):
            prev, result = result, []
            row = triangle[i]

            for j in range(i + 1):
                if j == 0 or (j < i and prev[j - 1] > prev[j]):
                    result.append(prev[j] + row[j])
                else:
                    result.append(prev[j - 1] + row[j])

        return min(result)
go
func minimumTotal(triangle [][]int) int {
	prev := []int{}
	result := triangle[0]

	for i := 1; i < len(triangle); i++ {
		prev = result
		result = []int{}
		row := triangle[i]

		for j := 0; j <= i; j++ {
			if j == 0 || (j < i && prev[j-1] > prev[j]) {
				result = append(result, prev[j]+row[j])
			} else {
				result = append(result, prev[j-1]+row[j])
			}
		}
	}

	min := result[0]
	for _, val := range result {
		if val < min {
			min = val
		}
	}
	return min
}