Minimum path sum

Array Dynamic Programming Matrix

67.8% acceptance

Jan 12, 2026

13611

201

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path. Note: You can only move either down or right at any point in time.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_path_sum(mut grid: Vec<Vec<i32>>) -> i32 {
    let m = grid.len();
    let n = grid[0].len();
    
    // Initialize first row
    for j in 1..n {
      grid[0][j] += grid[0][j-1];
    }
    
    // Initialize first column
    for i in 1..m {
      grid[i][0] += grid[i-1][0];
    }
    
    // Fill the dp table
    for i in 1..m {
      for j in 1..n {
        grid[i][j] += grid[i-1][j].min(grid[i][j-1]);
      }
    }
    
    grid[m-1][n-1]
  }
}