Start learning free

LESSON 302 OF 414 · MEMOIZATION

Minimum Path Sum in Rust: In-Place Dynamic Programming

Practice O(n2) - DP Read the full explanation

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.

Example:

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.
STEP 1 OF 6
    Ctrl + Enter to check

    RUST · MEMOIZATION

    Minimum Path Sum in Rust, explained

    Problem overview

    The function min_path_sum receives a grid of non-negative integers as a Vec<Vec<i32>> with n rows and m columns. A path goes from the top-left cell to the bottom-right cell, moving only down or right. The function returns the smallest sum of the numbers along such a path.

    For [[1, 3, 1], [1, 5, 1], [4, 2, 1]] the answer is 7, from the path 1, 3, 1, 1, 1.

    Approach: turn each cell into a running total

    Every path to a cell (i, j) arrives either from the cell above or from the cell to the left. So if best(i, j) is the cheapest way to reach (i, j) from the start, then:

    • best(0, 0) is the cell's own value;
    • in the first row, a cell can only come from its left neighbour, so best(0, j) = grid[0][j] + best(0, j - 1);
    • in the first column, a cell can only come from above, so best(i, 0) = grid[i][0] + best(i - 1, 0);
    • everywhere else, best(i, j) = grid[i][j] + min(best(i - 1, j), best(i, j - 1)).

    That is a table to fill row by row. Cells are visited in an order where the cell above and the cell to the left are already finished. Instead of allocating a second table, this lesson overwrites grid itself: after processing, grid[i][j] holds best(i, j), and the answer is the bottom-right cell.

    On the example, the first row becomes 1, 4, 5 and the first column becomes 1, 2, 6. The middle cell 5 adds the smaller of 4 (above) and 2 (left), so it becomes 7. The cell at row 1, column 2 adds the smaller of 5 and 7, giving 6. The cell at row 2, column 1 adds the smaller of 7 and 6, giving 8. The last cell, 1, adds the smaller of 6 and 8, giving 7.

    Step by step

    1. Make the grid mutable. The parameter isn't declared mut, so rebind it with let mut grid = grid;. The new variable takes over the same vector without copying it.
    2. Read the dimensions: n is the number of rows and m the number of columns.
    3. Fill the first row with a loop over j in 1..m, adding grid[0][j - 1] to grid[0][j]. Cell (0, 0) stays as it is.
    4. Fill the first column with a loop over i in 1..n, adding grid[i - 1][0] to grid[i][0].
    5. Fill the rest with two nested loops over 1..n and 1..m, adding the smaller of the cell above and the cell to the left.
    6. Return the corner, grid[n - 1][m - 1], as the final expression.

    The solution in Rust

    impl Solution {
    fn min_path_sum(grid: Vec<Vec<i32>>) -> i32 {
        let mut grid = grid;
        let n = grid.len();
        let m = grid[0].len();

        for j in 1..m {
            grid[0][j] += grid[0][j - 1];
        }

        for i in 1..n {
            grid[i][0] += grid[i - 1][0];
        }

        for i in 1..n {
            for j in 1..m {
                grid[i][j] += grid[i - 1][j].min(grid[i][j - 1]);
            }
        }

        grid[n - 1][m - 1]
    }
}

    The Rust details worth a closer look:

    • Shadowing. let mut grid = grid; declares a new variable with the same name, which hides the parameter. The vector is moved, not copied. Writing mut grid: Vec<Vec<i32>> in the signature would do the same job.
    • Ownership. The function takes the grid by value, so the caller gives it up. Changing it here doesn't affect any variable the caller still has. A caller that needs the original must pass a clone.
    • Ranges. 1..m starts at 1 and stops before m. When m is 1, the range is empty, so a grid with one column skips the first-row loop. The same holds for 1..n and a single row.
    • Compound assignment. grid[0][j] += grid[0][j - 1] reads one element and writes another. Both are plain i32 values, so the borrow checker accepts it.
    • The min method. grid[i - 1][j].min(grid[i][j - 1]) compares the two neighbours. The method call needs both operands to have the same type, i32.
    • Overflow. The totals are i32. A grid whose path sum exceeds 2,147,483,647 would wrap silently in an optimized build, and panic in a debug build.

    Complexity

    Time: O(n * m). Each cell is updated once: the two edge loops cover the first row and the first column, and the nested loops cover the remaining cells.

    Space: O(1) extra. The table is the grid itself, which the function already owns. Only a few integers are added. This is less memory than the memoized recursion of the previous lesson, which needed a separate cache and a call stack.

    Edge cases and common mistakes

    • A single cell. [[5]] gives 5: all the loops are empty and the corner is the start.
    • One row or one column. [[1, 2, 3]] and [[1], [2], [3]] give 6, the sum of all the cells.
    • All zeros. [[0, 0], [0, 0]] gives 0.
    • Empty grid. It isn't a valid input: reading grid[0] panics with an out-of-bounds error.
    • Starting the inner loops at 0. Then j - 1 and i - 1 would be computed on a usize equal to 0, which panics in a debug build and indexes out of bounds in an optimized one.
    • Using the original values. The neighbours must be the already updated totals, so the order matters. Row by row, left to right is correct.
    • Forgetting the edge loops. The middle formula would look for a cell above the first row or left of the first column.

    Testing

    • [[1, 3, 1], [1, 5, 1], [4, 2, 1]] gives 7.
    • [[5]] gives 5.
    • [[1, 2, 3]] gives 6.
    • [[1], [2], [3]] gives 6.
    • [[1, 2], [1, 1]] gives 3.
    Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free