Minimum Path Sum in Grid in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Minimum Path Sum Calculation

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

DSA Rust

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

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

A 7

B 8

C 9

D 6

💡 Hint

Trace the path with the smallest sum from top-left to bottom-right moving only down or right.

The minimum path sum is calculated by dynamic programming. The path is 1 -> 3 -> 1 -> 1 -> 1 with sum 7.

❓ Predict Output

intermediate

Minimum Path Sum for a 2x2 Grid

What is the output of this Rust function for the given 2x2 grid?

DSA Rust

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

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

A 3

B 2

C 4

D 5

💡 Hint

Consider the path 1 -> 1 -> 1 or 1 -> 2 -> 1.

The minimum path sum is 3 by going down then right or right then down.

🔧 Debug

advanced

Identify the Runtime Error in Minimum Path Sum Code

What error does the following Rust code produce when run with a non-rectangular grid?

DSA Rust

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

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

A No error, outputs 8

B Type mismatch error

C Index out of bounds panic

D Compilation error due to mismatched types

💡 Hint

Check if all rows have the same length before accessing grid[i][j].

The grid rows have different lengths, so accessing grid[1][2] causes an index out of bounds panic at runtime.

🧠 Conceptual

advanced

Why Use Dynamic Programming for Minimum Path Sum?

Why is dynamic programming the best approach to solve the minimum path sum problem in a grid?

A Because it uses recursion without storing intermediate results

B Because it breaks the problem into overlapping subproblems and stores results to avoid recomputation

C Because it randomly guesses the path and checks sums

D Because it sorts the grid cells and picks the smallest values

💡 Hint

Think about how the problem can be divided into smaller parts and how to avoid repeated work.

Dynamic programming solves the problem by computing minimum sums for smaller subgrids and reusing those results to build the solution for the full grid efficiently.

❓ Predict Output

expert

Output of Minimum Path Sum with Negative Values

What is the output of this Rust code that calculates the minimum path sum in a grid containing negative values?

DSA Rust

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

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

A 2

B 1

C -1

D 0

💡 Hint

Consider paths that include negative values to minimize the sum.

The minimum path sum is 0 by the path 1 -> -3 -> 2 -> -1 -> 1 with sum 0.

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