Minimum falling path sum

Array Dynamic Programming Matrix

60.8% acceptance

Feb 25, 2026

6971

174

Given an n x n array of integers matrix, return the minimum sum of any falling path through matrix. A falling path starts at any element in the first row and chooses the element in the next row that is either directly below or diagonally left/right. Specifically, the next element from position (row, col) will be (row + 1, col - 1), (row + 1, col), or (row + 1, col + 1).

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_falling_path_sum(matrix: Vec<Vec<i32>>) -> i32 {
    let n = matrix.len();
    let mut dp = matrix[0].clone();
    for row in 1..n {
      let prev = dp.clone();
      for col in 0..n {
        let left = if col > 0 { prev[col-1] } else { i32::MAX };
        let mid = prev[col];
        let right = if col + 1 < n { prev[col+1] } else { i32::MAX };
        dp[col] = matrix[row][col] + left.min(mid).min(right);
      }
    }
    *dp.iter().min().unwrap()
  }
}