# 19.01.2024 [931. Minimum Falling Path Sum]
Min sum moving bottom center, left, right in 2D matrix.
19.01.2024
931. Minimum Falling Path Sum medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/477
Problem TLDR
Min sum moving bottom center, left, right in 2D matrix.
Intuition
At every cell we must add it value to path plus min of a three direct top cells as they are the only way here.
Approach
We can reuse the matrix or better use separate temporal array.
Complexity
Time complexity:
O(mn)Space complexity:
O(1), or O(m) to not corrupt the inputs
Code
fun minFallingPathSum(matrix: Array<IntArray>): Int {
for (y in 1..<matrix.size) for (x in 0..<matrix[0].size)
matrix[y][x] += (max(0, x - 1)..min(x + 1, matrix[0].lastIndex))
.minOf { matrix[y - 1][it] }
return matrix.last().min()
}
pub fn min_falling_path_sum(matrix: Vec<Vec<i32>>) -> i32 {
*matrix.into_iter().reduce(|dp, row|
row.iter().enumerate().map(|(x, &v)|
v + dp[x.max(1) - 1..=(x + 1).min(dp.len() - 1)]
.iter().min().unwrap()
).collect()
).unwrap().iter().min().unwrap()
}