Minimum Path Sum in Grid in DSA Rust

Mental Model

Find the smallest total by moving only right or down from the top-left to the bottom-right of a grid.

Analogy: Imagine walking through a city grid where each block has a cost to cross. You want to spend the least energy walking from your home (top-left) to your friend's house (bottom-right), moving only east or south.

Start:
[1] -> [3] -> [1]
 ↓      ↓      ↓
[1] -> [5] -> [1]
 ↓      ↓      ↓
[4] -> [2] -> [1]

You can only move -> or ↓ to reach the bottom-right.

Dry Run Walkthrough

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]

Goal: Find the path from top-left to bottom-right with the smallest sum of numbers, moving only right or down.

Step 1: Start at top-left cell (0,0) with value 1

[1] -> [3] -> [1]
 ↓      ↓      ↓
[1] -> [5] -> [1]
 ↓      ↓      ↓
[4] -> [2] -> [1]

Why: We begin from the starting point with initial cost 1.

Step 2: Calculate minimum path sums for first row by moving right

[1] -> [4] -> [5]
 ↓      ↓      ↓
[1] -> [5] -> [1]
 ↓      ↓      ↓
[4] -> [2] -> [1]

Why: Only right moves allowed in first row, so sums accumulate.

Step 3: Calculate minimum path sums for first column by moving down

[1] -> [4] -> [5]
 ↓      ↓      ↓
[2] -> [5] -> [1]
 ↓      ↓      ↓
[6] -> [2] -> [1]

Why: Only down moves allowed in first column, so sums accumulate.

Step 4: Calculate minimum path sum for cell (1,1) by choosing min from top or left

[1] -> [4] -> [5]
 ↓      ↓      ↓
[2] -> [7] -> [1]
 ↓      ↓      ↓
[6] -> [2] -> [1]

Why: Choose smaller sum between top (4) and left (2), add current cell (5).

Step 5: Calculate minimum path sum for cell (1,2)

[1] -> [4] -> [5]
 ↓      ↓      ↓
[2] -> [7] -> [6]
 ↓      ↓      ↓
[6] -> [2] -> [1]

Why: Choose min between top (5) and left (7), add current cell (1).

Step 6: Calculate minimum path sum for cell (2,1)

[1] -> [4] -> [5]
 ↓      ↓      ↓
[2] -> [7] -> [6]
 ↓      ↓      ↓
[6] -> [9] -> [1]

Why: Choose min between top (7) and left (6), add current cell (2).

Step 7: Calculate minimum path sum for bottom-right cell (2,2)

[1] -> [4] -> [5]
 ↓      ↓      ↓
[2] -> [7] -> [6]
 ↓      ↓      ↓
[6] -> [9] -> [7]

Why: Choose min between top (6) and left (9), add current cell (1).

Result:

Final grid with minimum path sums:
[1] -> [4] -> [5]
 ↓      ↓      ↓
[2] -> [7] -> [6]
 ↓      ↓      ↓
[6] -> [9] -> [7]
Minimum path sum = 7

Annotated Code

DSA Rust

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

    // Update first row sums
    for j in 1..n {
        grid[0][j] += grid[0][j - 1];
    }

    // Update first column sums
    for i in 1..m {
        grid[i][0] += grid[i - 1][0];
    }

    // Update rest of the grid
    for i in 1..m {
        for j in 1..n {
            grid[i][j] += std::cmp::min(grid[i - 1][j], grid[i][j - 1]);
        }
    }

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

fn main() {
    let mut grid = vec![
        vec![1, 3, 1],
        vec![1, 5, 1],
        vec![4, 2, 1],
    ];
    let result = min_path_sum(&mut grid);
    for row in &grid {
        for val in row {
            print!("{} ", val);
        }
        println!();
    }
    println!("Minimum path sum = {}", result);
}

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

Accumulate sums along the first row by adding left neighbor

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

Accumulate sums along the first column by adding top neighbor

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

For each cell, add the minimum of top or left neighbor sums

Output

1 4 5 

2 7 6 

6 9 7 

Minimum path sum = 7

Complexity Analysis

Time: O(m*n) because we visit each cell once to compute minimum sums

Space: O(1) because we update the grid in place without extra storage

vs Alternative: Naive recursive approach would be exponential due to repeated calculations; this dynamic programming approach is efficient and uses constant extra space.

Edge Cases

Empty grid

Function may panic or return 0 if handled; here it assumes non-empty grid

DSA Rust

let m = grid.len(); let n = grid[0].len();

Single cell grid

Returns the value of the single cell as minimum path sum

DSA Rust

for j in 1..n { ... } and for i in 1..m { ... } loops skip since m or n is 1

Grid with all equal values

Minimum path sum is sum along any path moving right and down

DSA Rust

std::cmp::min(grid[i - 1][j], grid[i][j - 1]) chooses minimum correctly

When to Use This Pattern

When you see a grid and need to find a path with minimum cost moving only right or down, use dynamic programming to build up minimum sums from the start.

Common Mistakes

Mistake: Not updating the first row and first column separately before filling the rest
Fix: Initialize first row and first column sums before processing inner cells

Mistake: Using max instead of min when choosing between top and left neighbors
Fix: Use std::cmp::min to pick the smaller sum for minimum path

Summary

Calculates the smallest sum path from top-left to bottom-right in a grid moving only right or down.

Use when you need to find minimum cost paths in grid-like problems with restricted moves.

Build the solution by accumulating minimum sums row-wise and column-wise, then fill the rest using the minimum of top and left neighbors.

Practice

1. What does the "Minimum Path Sum in Grid" problem ask you to find?
Given a grid of numbers, find the path from top-left to bottom-right with the smallest sum.

easy

A. The path with the largest sum of numbers from top-left to bottom-right

B. The maximum number in the grid

C. The number of paths from top-left to bottom-right

D. The path with the smallest sum of numbers from top-left to bottom-right

Solution

1. Step 1: Understand the problem goal

   The problem asks to find a path from the top-left corner to the bottom-right corner of a grid that has the smallest sum of all numbers along the path.

2. Step 2: Clarify path rules

   Movement is only allowed down or right at any point, so the path must be continuous and only move in these directions.

3. Final Answer:

   The path with the smallest sum of numbers from top-left to bottom-right -> Option D

4. Quick Check:

   Minimum path sum means smallest total sum [OK]

Hint: Look for smallest sum path from top-left to bottom-right [OK]

Common Mistakes:

• Confusing minimum with maximum sum
• Counting number of paths instead of sum
• Ignoring movement restrictions (only right/down)

2. Which Rust code snippet correctly initializes a 2D vector grid with values for the Minimum Path Sum problem?

easy

A. let grid = vec![vec![1, 3, 1], vec![1, 5, 1], vec![4, 2, 1]];

B. let grid = [1, 3, 1, 1, 5, 1, 4, 2, 1];

C. let grid = vec![1, 3, 1; 1, 5, 1; 4, 2, 1];

D. let grid = vec![[1, 3, 1], [1, 5, 1], [4, 2, 1]];

Solution

1. Step 1: Identify correct 2D vector syntax in Rust

   Rust uses vec![vec![...], vec![...], ...] to create a 2D vector. let grid = vec![vec![1, 3, 1], vec![1, 5, 1], vec![4, 2, 1]]; uses this correct syntax.

2. Step 2: Check other options for errors

   let grid = [1, 3, 1, 1, 5, 1, 4, 2, 1]; is a 1D array, not 2D. let grid = vec![1, 3, 1; 1, 5, 1; 4, 2, 1]; uses invalid syntax with semicolons inside vec!. let grid = vec![[1, 3, 1], [1, 5, 1], [4, 2, 1]]; uses nested arrays inside vec! which is invalid.

3. Final Answer:

   let grid = vec![vec![1, 3, 1], vec![1, 5, 1], vec![4, 2, 1]]; -> Option A

4. Quick Check:

   vec![vec![...], vec![...]] creates 2D vector [OK]

Hint: Use vec![vec![...], vec![...]] for 2D vectors in Rust [OK]

Common Mistakes:

• Using semicolons inside vec! macro
• Confusing 1D and 2D vector syntax
• Using arrays inside vec! without vec! wrapper

3. What is the output of this Rust code that calculates the minimum path sum in a 3x3 grid?

fn min_path_sum(grid: &mut Vec) -> i32 {
    let m = grid.len();
    let n = grid[0].len();
    for i in 1..m {
        grid[i][0] += grid[i - 1][0];
    }
    for j in 1..n {
        grid[0][j] += grid[0][j - 1];
    }
    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]
}

fn main() {
    let mut grid = vec![
        vec![1, 3, 1],
        vec![1, 5, 1],
        vec![4, 2, 1],
    ];
    println!("{}", min_path_sum(&mut grid));
}

medium

A. 9

B. 7

C. 8

D. 10

Solution

1. Step 1: Calculate first column cumulative sums

   grid[1][0] = 1 + 1 = 2, grid[2][0] = 4 + 2 = 6

2. Step 2: Calculate first row cumulative sums

   grid[0][1] = 3 + 1 = 4, grid[0][2] = 1 + 4 = 5

3. Step 3: Calculate remaining cells

   grid[1][1] = 5 + min(4,2) = 5 + 2 = 7, grid[1][2] = 1 + min(5,7) = 1 + 5 = 6, grid[2][1] = 2 + min(7,6) = 2 + 6 = 8, grid[2][2] = 1 + min(6,8) = 1 + 6 = 7

4. Final Answer:

   7 -> Option B

5. Quick Check:

   Minimum path sum = 7 [OK]

Hint: Add min of top or left cell to current cell [OK]

Common Mistakes:

• Not updating first row and column sums correctly
• Adding max instead of min of neighbors
• Mixing indices in loops

4. Identify the bug in this Rust function for minimum path sum and select the fix:

fn min_path_sum(grid: &mut Vec) -> i32 {
    let m = grid.len();
    let n = grid[0].len();
    for i in 1..m {
        grid[i][0] = grid[i - 1][0]; // Bug here
    }
    for j in 1..n {
        grid[0][j] += grid[0][j - 1];
    }
    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]
}

medium

A. Change grid[i][j] += grid[i - 1][j].min(grid[i][j - 1]); to grid[i][j] = grid[i - 1][j].max(grid[i][j - 1]);

B. Change grid[0][j] += grid[0][j - 1]; to grid[0][j] = grid[0][j - 1];

C. Change grid[i][0] = grid[i - 1][0]; to grid[i][0] += grid[i - 1][0];

D. No bug, code is correct

Solution

1. Step 1: Check first column update

   The line grid[i][0] = grid[i - 1][0]; overwrites the current cell instead of adding the previous sum, so it loses the current cell's value.

2. Step 2: Correct the update to accumulate sums

   It should be grid[i][0] += grid[i - 1][0]; to add the previous cell's sum to the current cell's value.

3. Final Answer:

   Change grid[i][0] = grid[i - 1][0]; to grid[i][0] += grid[i - 1][0]; -> Option C

4. Quick Check:

   First column sums must accumulate [OK]

Hint: Add previous cell value, don't overwrite it [OK]

Common Mistakes:

• Overwriting instead of adding in first column
• Changing correct addition in first row
• Using max instead of min for path sum

5. Given a 4x4 grid:

[[1, 3, 1, 2],
 [1, 5, 1, 1],
 [4, 2, 1, 3],
 [2, 1, 2, 1]]

What is the minimum path sum from top-left to bottom-right moving only right or down?

hard

A. 10

B. 11

C. 12

D. 13

Solution

1. Step 1: Calculate first row and column cumulative sums

   First row: [1, 4, 5, 7]
   First column: [1, 2, 6, 8]

2. Step 2: Calculate inner cells using min of top or left

   Row 1: grid[1][1] = 5 + min(4,2) = 7
   grid[1][2] = 1 + min(5,7) = 6
   grid[1][3] = 1 + min(7,6) = 7
   Row 2: grid[2][1] = 2 + min(7,6) = 8
   grid[2][2] = 1 + min(6,8) = 7
   grid[2][3] = 3 + min(7,7) = 10
   Row 3: grid[3][1] = 1 + min(8,8) = 9
   grid[3][2] = 2 + min(7,9) = 9
   grid[3][3] = 1 + min(10,9) = 10

3. Step 3: Final minimum path sum

   The bottom-right cell value is 10, but we must check carefully:
   Recalculate carefully:
   First row: 1,4,5,7
   First col: 1,2,6,8
   grid[1][1] = 5 + min(4,2) = 5 + 2 = 7
   grid[1][2] = 1 + min(5,7) = 1 + 5 = 6
   grid[1][3] = 1 + min(7,6) = 1 + 6 = 7
   grid[2][1] = 2 + min(7,6) = 2 + 6 = 8
   grid[2][2] = 1 + min(6,8) = 1 + 6 = 7
   grid[2][3] = 3 + min(7,7) = 3 + 7 = 10
   grid[3][1] = 1 + min(8,8) = 1 + 8 = 9
   grid[3][2] = 2 + min(7,9) = 2 + 7 = 9
   grid[3][3] = 1 + min(10,9) = 1 + 9 = 10

4. Final Answer:

   10 -> Option A

5. Quick Check:

   Bottom-right cell after DP = 10 [OK]

Hint: Build sums row-wise and column-wise, then fill inner cells [OK]

Common Mistakes:

• Miscomputing min between top and left cells
• Forgetting to update first row or column sums
• Adding max instead of min