Start learning free

LESSON 292 OF 414 · BACKTRACKING

Minimum Path Sum in Rust: Recursive Search on a Grid

Practice O(2n) 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.

Note:

This plain recursive solution recomputes the same cells many times, so it runs in exponential time, O(2n + m), and uses O(n + m) extra space for the recursion stack.

STEP 1 OF 7
    Ctrl + Enter to check

    RUST · BACKTRACKING

    Minimum Path Sum in Rust, explained

    Problem overview

    The function min_path_sum receives a grid of non-negative integers, grid, as a Vec<Vec<i32>>. A path starts at the top-left cell and ends at the bottom-right cell, and each move goes either one cell down or one cell right. The cost of a path is the sum of the numbers on every cell it visits, including the first and the last. The function returns the smallest possible cost.

    For the grid

    1 3 1
1 5 1
4 2 1

    the answer is 7, from the path 1, 3, 1, 1, 1 (right, right, down, down). Other paths cost more; for example, going down first and then right visits 1, 1, 4, 2, 1 for a total of 9.

    Approach: the best path from a cell is the cell plus the better of two continuations

    Define min_sum(grid, i, j) as the cost of the cheapest path from cell (i, j) to the bottom-right corner. Then:

    • At the bottom-right cell the path is that cell alone, so the answer is grid[i][j].
    • Anywhere else, the path continues either down to (i + 1, j) or right to (i, j + 1). The cost is grid[i][j] plus the smaller of the two continuations' costs.
    • At the bottom row only the move right exists, and at the last column only the move down. A move off the grid must never be chosen, so it is given the cost i32::MAX, the largest i32, which loses against any real cost.

    The answer to the problem is min_sum(grid, 0, 0). Each call moves down or right, so the calls always end at the corner.

    This lesson is in the backtracking chapter and its solution tries all paths. The statement mentions O(n * m), which a version that remembers its answers reaches, but this recursive version is slower, as the complexity section explains.

    Step by step

    1. Declare min_sum above min_path_sum. It borrows the grid as &Vec<Vec<i32>>, takes i and j as usize, and returns an i32.
    2. Read the dimensions: n is the number of rows and m the number of columns of the first row. Both come from len() and are usize.
    3. Base case. If i == n - 1 && j == m - 1, return grid[i][j].
    4. Cost of going down. If i + 1 < n, it is the recursive call at (i + 1, j). Otherwise it is i32::MAX. An if/else is an expression, so its value is assigned straight to down.
    5. Cost of going right, the same way, with j + 1 < m.
    6. Combine. The result is grid[i][j] + down.min(right), as the final expression without a semicolon.
    7. Start from min_path_sum: Self::min_sum(&grid, 0, 0). The &grid lends the grid and every path starts in the top-left cell.

    The solution in Rust

    impl Solution {
    fn min_sum(grid: &Vec<Vec<i32>>, i: usize, j: usize) -> i32 {
        let n = grid.len();
        let m = grid[0].len();
        if i == n - 1 && j == m - 1 {
            return grid[i][j];
        }
        let down = if i + 1 < n {
            Self::min_sum(grid, i + 1, j)
        } else {
            i32::MAX
        };
        let right = if j + 1 < m {
            Self::min_sum(grid, i, j + 1)
        } else {
            i32::MAX
        };
        grid[i][j] + down.min(right)
    }

    fn min_path_sum(grid: Vec<Vec<i32>>) -> i32 {
        Self::min_sum(&grid, 0, 0)
    }
}

    The Rust details worth a closer look:

    • i32::MAX as "infinity". It is a constant for the largest i32, 2147483647. Adding to it would overflow, which wraps silently in the optimized build the lessons use and panics in a debug build. That never happens here: at most one of down and right is i32::MAX, because both are only at the bottom-right corner, and the base case has already returned there. And min picks the real cost, so i32::MAX is never added to anything.
    • if as an expression. let down = if cond { a } else { b }; has no separate assignments in each branch. Both branches must have the same type, i32 here, and neither ends with a semicolon.
    • Comparing before adding. The check i + 1 < n is written this way, instead of i < n - 1, to avoid subtracting from a usize. The base case does use n - 1, which is fine for a non-empty grid.
    • Indexing. grid[i][j] needs usize indexes. Out-of-bounds access would panic, which is why the moves are checked first.
    • Borrowing. grid inside min_sum is already a reference, so the recursive calls pass it as it is. Only reads happen, so a shared reference is enough.
    • Self::. Neither function takes self, so they are called through Self::.

    Complexity

    Let the grid have n rows and m columns.

    Time: exponential. Every call that isn't at an edge makes two calls, and the function doesn't remember the answer for a cell it has already solved. The same cell is reached through many different routes, and the number of calls grows with the number of paths. The 3x3 example makes 19 calls. A 10x10 grid makes 184,755 calls, a 12x12 grid makes 2,704,155 and a 14x14 grid makes 40,116,599. Each added row and column multiplies the work by about four.

    To reach the O(n * m) time of the statement, store the answer of each cell the first time it is computed, or fill a table from the bottom-right corner backwards. There are only n * m different cells, and each one needs a constant amount of work.

    Space: O(n + m) for the recursion. Each call moves one step down or right, so the deepest chain has n + m - 1 calls. The grid is borrowed, not copied.

    Edge cases and common mistakes

    • One cell. A grid [[5]] returns 5: the start is the end.
    • One row or one column. [[1, 2, 3]] and [[1], [2], [3]] both return 6, as there is only one path. The off-grid moves are replaced by i32::MAX, so the real direction always wins.
    • Counting the first and last cells. Both are part of the path. In the example, 7 includes the 1 at the top-left and the 1 at the bottom-right.
    • Taking the greedy choice. Always stepping onto the cheaper neighbour can fail. In [[1, 2, 9], [3, 9, 9], [3, 1, 1]] the cheaper first step is to the 2, and every path that starts that way costs at least 14, while going down first costs 9. The recursion compares whole paths, not single steps.
    • Using 0 instead of a large value for off-grid moves. A move off the grid would look free and always be chosen.
    • Empty grid. grid[0] panics for an empty vector, so the function assumes at least one row.

    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