LeetCode Entry
1289. Minimum Falling Path Sum II
Min non-direct path top down in a 2D matrix programming
1289. Minimum Falling Path Sum II hard
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/584
Problem TLDR
Min non-direct path top down in a 2D matrix #hard #dynamic_programming
Intuition
Let’s try an example:
On each row we need to know the min value from the previous row, or the second min, if first is directly up. Then adding this min to the current cell would give us the min-sum.
Approach
We can reuse the matrix for brevety, however don’t do this in the interview or in a production code.
Complexity
-
Time complexity: \(O(nm)\)
-
Space complexity: \(O(1)\), or O(m) if the separate array used
Code
fun minFallingPathSum(grid: Array<IntArray>): Int {
var min1 = -1; var min2 = -1
for (y in grid.indices) { grid[y].let {
if (y > 0) for (x in it.indices)
it[x] += grid[y - 1][if (x == min1) min2 else min1]
min1 = -1; min2 = -1
for (x in it.indices)
if (min1 < 0 || it[x] < it[min1]) {
min2 = min1; min1 = x
} else if (min2 < 0 || it[x] < it[min2]) min2 = x
}}
return grid.last()[min1]
}
pub fn min_falling_path_sum(mut grid: Vec<Vec<i32>>) -> i32 {
let n = grid[0].len(); let (mut min1, mut min2) = (n, n);
for y in 0..grid.len() {
if y > 0 { for x in 0..n {
grid[y][x] += grid[y - 1][if x == min1 { min2 } else { min1 }]
}}
min1 = n; min2 = n;
for x in 0..n {
if min1 == n || grid[y][x] < grid[y][min1] {
min2 = min1; min1 = x
} else if min2 == n || grid[y][x] < grid[y][min2] { min2 = x }
}
}
grid[grid.len() - 1][min1]
}