LeetCode Entry
931. Minimum Falling Path Sum
Min sum moving bottom center, left, right in 2D matrix.
931. Minimum Falling Path Sum medium
blog post
substack
youtube
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()
}