Min Total In 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.

Source

package questions

import _utils.UseCommentAsDocumentation
import utils.shouldBe
import kotlin.math.min

/**
 * 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.
 *
 * [Source](https://leetcode.com/problems/triangle/)
 */
@UseCommentAsDocumentation
fun minimumTotal(triangle: List<List<Int>>): Int {
    val minCumulativeSumTriangle = MutableList<MutableList<Int?>>(triangle.size) {
        MutableList(it + 1) { null }
    }
    minCumulativeSumTriangle[0][0] = triangle[0][0] // initialize
    for (row in 1..triangle.lastIndex) {
        for (col in 0..triangle.last().lastIndex) {
            val currentValue = triangle.getOrNull(row)?.getOrNull(col) ?: continue

            // get previous row's col-1 and col
            // then sum it with currentValue
            // take the minimum of the two
            val minCumulativeSumYet = min(
                minCumulativeSumTriangle[row - 1].getOrNull(col)?.plus(currentValue) ?: Int.MAX_VALUE,
                minCumulativeSumTriangle[row - 1].getOrNull(col - 1)?.plus(currentValue) ?: Int.MAX_VALUE
            )
            minCumulativeSumTriangle[row][col] = minCumulativeSumYet
        }
    }
    // answer is minimum value in the last row
    return minCumulativeSumTriangle.last().filterNotNull().minOrNull()!!
}

fun main() {
    minimumTotal(listOf(listOf(2), listOf(3, 4), listOf(6, 5, 7), listOf(4, 1, 8, 3))) shouldBe 11
    minimumTotal(listOf(listOf(-10))) shouldBe -10
}

---

View on GitHub

Updated on 2022-08-21