Minimum falling path sum ii

Array Dynamic Programming Matrix

63.2% acceptance

Feb 25, 2026

2372

124

Given an n x n integer matrix grid, return the minimum sum of a falling path with non-zero shifts. A falling path with non-zero shifts is a choice of exactly one element from each row of grid such that no two elements chosen in adjacent rows are in the same column.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_falling_path_sum(grid: Vec<Vec<i32>>) -> i32 {
    let n = grid.len();
    if n == 1 { return grid[0][0]; }

    let mut dp = grid[0].clone();
    for i in 1..n {
      let (min1_val, min1_idx) = dp.iter().enumerate()
        .min_by_key(|&(_, &v)| v)
        .map(|(i, &v)| (v, i))
        .unwrap();
      let (min2_val, _) = dp.iter().enumerate()
        .filter(|&(i, _)| i != min1_idx)
        .min_by_key(|&(_, &v)| v)
        .map(|(i, &v)| (v, i))
        .unwrap();
      let mut new_dp = vec![0; n];
      for j in 0..n {
        let best = if j != min1_idx { min1_val } else { min2_val };
        new_dp[j] = grid[i][j] + best;
      }
      dp = new_dp;
    }
    *dp.iter().min().unwrap()
  }
}