793 Intermediate

793-minimum-path-sum — Minimum Path Sum

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "793-minimum-path-sum — Minimum Path Sum" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Finding the minimum-cost path through a grid from the top-left to the bottom-right (moving only right or down) is a fundamental 2D DP problem. Key difference from OCaml: 1. **In

Tutorial

The Problem

Finding the minimum-cost path through a grid from the top-left to the bottom-right (moving only right or down) is a fundamental 2D DP problem. It models route planning in robotics, game pathfinding with terrain costs, circuit board wiring, and is a building block for more complex grid DP problems. The constraint of only moving right or down makes it solvable in O(mn) with O(1) extra space (modifying the grid in place).

🎯 Learning Outcomes

• Initialize boundary conditions: first row and column are prefix sums (no choice)

• Apply the 2D recurrence: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

• Optimize space by modifying the grid in-place or using a rolling row

• Understand the difference from A* pathfinding (no heuristic needed here)

• Reconstruct the actual path by backtracking from dp[m-1][n-1]

Code Example

#![allow(clippy::all)]
//! # Minimum Path Sum

pub fn min_path_sum(grid: &[Vec<i32>]) -> i32 {
    if grid.is_empty() || grid[0].is_empty() {
        return 0;
    }
    let (m, n) = (grid.len(), grid[0].len());
    let mut dp = vec![vec![0; n]; m];
    dp[0][0] = grid[0][0];
    for j in 1..n {
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }
    for i in 1..m {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }
    for i in 1..m {
        for j in 1..n {
            dp[i][j] = grid[i][j] + dp[i - 1][j].min(dp[i][j - 1]);
        }
    }
    dp[m - 1][n - 1]
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_path() {
        let grid = vec![vec![1, 3, 1], vec![1, 5, 1], vec![4, 2, 1]];
        assert_eq!(min_path_sum(&grid), 7);
    }
}

(* Minimum Path Sum — in-place DP, O(m×n) time, O(1) extra space *)

let min_path_sum grid =
  let m = Array.length grid in
  if m = 0 then 0
  else begin
    let n = Array.length grid.(0) in
    let g = Array.init m (fun i -> Array.copy grid.(i)) in
    (* Fill first row *)
    for j = 1 to n - 1 do
      g.(0).(j) <- g.(0).(j) + g.(0).(j-1)
    done;
    (* Fill first col *)
    for i = 1 to m - 1 do
      g.(i).(0) <- g.(i).(0) + g.(i-1).(0)
    done;
    (* Fill rest *)
    for i = 1 to m - 1 do
      for j = 1 to n - 1 do
        g.(i).(j) <- g.(i).(j) + min g.(i-1).(j) g.(i).(j-1)
      done
    done;
    g.(m-1).(n-1)
  end

(* Reconstruct the actual path *)
let min_path_reconstruct grid =
  let m = Array.length grid in
  let n = Array.length grid.(0) in
  let g = Array.init m (fun i -> Array.copy grid.(i)) in
  for j = 1 to n - 1 do g.(0).(j) <- g.(0).(j) + g.(0).(j-1) done;
  for i = 1 to m - 1 do g.(i).(0) <- g.(i).(0) + g.(i-1).(0) done;
  for i = 1 to m - 1 do
    for j = 1 to n - 1 do
      g.(i).(j) <- g.(i).(j) + min g.(i-1).(j) g.(i).(j-1)
    done
  done;
  let path = ref [] in
  let i = ref (m-1) and j = ref (n-1) in
  while !i > 0 || !j > 0 do
    path := (!i, !j) :: !path;
    if !i = 0 then decr j
    else if !j = 0 then decr i
    else if g.(!i-1).(!j) < g.(!i).(!j-1) then decr i
    else decr j
  done;
  path := (0,0) :: !path;
  (!path, g.(m-1).(n-1))

let () =
  let grid = [| [|1;3;1|]; [|1;5;1|]; [|4;2;1|] |] in
  Printf.printf "Min path sum: %d\n" (min_path_sum grid);
  let (path, cost) = min_path_reconstruct grid in
  Printf.printf "Path (cost=%d): " cost;
  List.iter (fun (r,c) -> Printf.printf "(%d,%d) " r c) path;
  print_newline ()

Key Differences

In-place optimization: Rust can modify the input grid directly (if mutable) to achieve O(1) extra space; OCaml's immutable arrays require a copy.

Rolling array: Both languages support a rolling 1D array optimization reducing space from O(mn) to O(n).

Path reconstruction: Both backtrack from the bottom-right, comparing neighbors to trace the minimum path.

Generalization: This problem generalizes to arbitrary DAG shortest paths — the 2D grid DAG constraint makes it DP-solvable; general DAGs require Bellman-Ford.

OCaml Approach

OCaml implements with Array.make_matrix m n 0 and fills boundary conditions explicitly. The 2D iteration uses nested for loops. Functional style can use Array.init m (fun i -> Array.init n (fun j -> ...)) but requires careful ordering for dependency correctness. The OCaml min function and array access patterns are idiomatic.

Full Source

#![allow(clippy::all)]
//! # Minimum Path Sum

pub fn min_path_sum(grid: &[Vec<i32>]) -> i32 {
    if grid.is_empty() || grid[0].is_empty() {
        return 0;
    }
    let (m, n) = (grid.len(), grid[0].len());
    let mut dp = vec![vec![0; n]; m];
    dp[0][0] = grid[0][0];
    for j in 1..n {
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }
    for i in 1..m {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }
    for i in 1..m {
        for j in 1..n {
            dp[i][j] = grid[i][j] + dp[i - 1][j].min(dp[i][j - 1]);
        }
    }
    dp[m - 1][n - 1]
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_path() {
        let grid = vec![vec![1, 3, 1], vec![1, 5, 1], vec![4, 2, 1]];
        assert_eq!(min_path_sum(&grid), 7);
    }
}

(* Minimum Path Sum — in-place DP, O(m×n) time, O(1) extra space *)

let min_path_sum grid =
  let m = Array.length grid in
  if m = 0 then 0
  else begin
    let n = Array.length grid.(0) in
    let g = Array.init m (fun i -> Array.copy grid.(i)) in
    (* Fill first row *)
    for j = 1 to n - 1 do
      g.(0).(j) <- g.(0).(j) + g.(0).(j-1)
    done;
    (* Fill first col *)
    for i = 1 to m - 1 do
      g.(i).(0) <- g.(i).(0) + g.(i-1).(0)
    done;
    (* Fill rest *)
    for i = 1 to m - 1 do
      for j = 1 to n - 1 do
        g.(i).(j) <- g.(i).(j) + min g.(i-1).(j) g.(i).(j-1)
      done
    done;
    g.(m-1).(n-1)
  end

(* Reconstruct the actual path *)
let min_path_reconstruct grid =
  let m = Array.length grid in
  let n = Array.length grid.(0) in
  let g = Array.init m (fun i -> Array.copy grid.(i)) in
  for j = 1 to n - 1 do g.(0).(j) <- g.(0).(j) + g.(0).(j-1) done;
  for i = 1 to m - 1 do g.(i).(0) <- g.(i).(0) + g.(i-1).(0) done;
  for i = 1 to m - 1 do
    for j = 1 to n - 1 do
      g.(i).(j) <- g.(i).(j) + min g.(i-1).(j) g.(i).(j-1)
    done
  done;
  let path = ref [] in
  let i = ref (m-1) and j = ref (n-1) in
  while !i > 0 || !j > 0 do
    path := (!i, !j) :: !path;
    if !i = 0 then decr j
    else if !j = 0 then decr i
    else if g.(!i-1).(!j) < g.(!i).(!j-1) then decr i
    else decr j
  done;
  path := (0,0) :: !path;
  (!path, g.(m-1).(n-1))

let () =
  let grid = [| [|1;3;1|]; [|1;5;1|]; [|4;2;1|] |] in
  Printf.printf "Min path sum: %d\n" (min_path_sum grid);
  let (path, cost) = min_path_reconstruct grid in
  Printf.printf "Path (cost=%d): " cost;
  List.iter (fun (r,c) -> Printf.printf "(%d,%d) " r c) path;
  print_newline ()

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_path() {
        let grid = vec![vec![1, 3, 1], vec![1, 5, 1], vec![4, 2, 1]];
        assert_eq!(min_path_sum(&grid), 7);
    }
}

Deep Comparison

OCaml vs Rust: Minimum Path Sum

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Implement min_path_sum_with_path(grid) -> (i32, Vec<(usize,usize)>) that returns both the minimum sum and the actual path as a list of coordinates.

Modify to allow movement in all four directions (with a cycle-detection constraint) and compare the complexity with the restricted problem.

Implement the in-place variant that modifies grid directly and uses O(1) extra space. Note any aliasing concerns.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust