LeetCode Entry

120. Triangle

25.09.2025 medium 2025 kotlin rust

Min path sum in triangle

120. Triangle medium blog post substack youtube

1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1123

Problem TLDR

Min path sum in triangle #medium #dp

Intuition

Go from top to bottom, keeping the previous result: curr[i] = t[j][i] + min(prev[i], prev[i-1])

Approach

  • careful with out of bounds exceptions
  • use Int.MAX_VALUE / 200

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(n)\)

Code


// 19ms
    fun minimumTotal(t: List<List<Int>>) = t.drop(1)
    .fold(t[0]) { p,t -> listOf(p[0] + t[0]) + (1..<t.size)
        .map { i-> t[i]+min(p[min(i, p.size-1)],p[i-1])}}.min()



// 0ms
    pub fn minimum_total(t: Vec<Vec<i32>>) -> i32 {
        t.iter().skip(1).fold(vec![t[0][0]], |p, r| { once(p[0]+r[0])
            .chain((1..r.len()).map(|i| r[i]+p[i.min(p.len()-1)].min(p[i-1]))).collect()
        }).into_iter().min().unwrap()
    }