Minimum Path Sum in Grid in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the first cell of the dp grid with the grid's first cell value.

DSA Rust

let mut dp = vec![vec![0; grid[0].len()]; grid.len()];
dp[0][0] = [1];

Drag options to blanks, or click blank then click option'

Adp[0][0]

Bgrid[0][0]

C1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Setting dp[0][0] to 0 instead of grid[0][0]

Using dp[0][0] on the right side causing self-reference

The minimum path sum at the starting cell is the value of the grid's first cell itself.

2fill in blank

medium

Complete the code to fill the first row of dp by accumulating sums from the left.

DSA Rust

for j in 1..grid[0].len() {
    dp[0][j] = dp[0][j - 1] + [1];
}

Drag options to blanks, or click blank then click option'

Agrid[j][0]

Bdp[0][j]

Cgrid[0][j]

Ddp[j][0]

Attempts:

3 left

💡 Hint

Common Mistakes

Using dp[0][j] on the right side causing incorrect accumulation

Using grid[j][0] which is from the first column, not row

Each cell in the first row accumulates the sum from the left cell plus the current grid cell value.

3fill in blank

hard

Fix the error in the code to fill the first column of dp by accumulating sums from above.

DSA Rust

for i in 1..grid.len() {
    dp[i][0] = dp[i - 1][0] + [1];
}

Drag options to blanks, or click blank then click option'

Adp[i][0]

Bgrid[0][i]

Cdp[0][i]

Dgrid[i][0]

Attempts:

3 left

💡 Hint

Common Mistakes

Using dp[i][0] on the right side causing incorrect accumulation

Using grid[0][i] which is from the first row, not column

Each cell in the first column accumulates the sum from the above cell plus the current grid cell value.

4fill in blank

hard

Fill both blanks to compute the minimum path sum for each cell inside the grid.

DSA Rust

for i in 1..grid.len() {
    for j in 1..grid[0].len() {
        dp[i][j] = grid[i][j] + dp[i - 1][j][1]dp[i][j - 1];
    }
}

Drag options to blanks, or click blank then click option'

A.min(

B+

C-

D*

Attempts:

3 left

💡 Hint

Common Mistakes

Using + instead of .min() causing incorrect sums

Using * or - which are not correct for minimum calculation

We add the current grid cell value to the minimum of the top and left dp cells.

5fill in blank

hard

Fill all three blanks to return the minimum path sum from top-left to bottom-right.

DSA Rust

fn min_path_sum(grid: Vec<Vec<i32>>) -> i32 {
    let mut dp = vec![vec![0; grid[0].len()]; grid.len()];
    dp[0][0] = [1];
    for j in 1..grid[0].len() {
        dp[0][j] = dp[0][j - 1] + [2];
    }
    for i in 1..grid.len() {
        dp[i][0] = dp[i - 1][0] + [3];
    }
    for i in 1..grid.len() {
        for j in 1..grid[0].len() {
            dp[i][j] = grid[i][j] + dp[i - 1][j].min(dp[i][j - 1]);
        }
    }
    dp[grid.len() - 1][grid[0].len() - 1]
}

Drag options to blanks, or click blank then click option'

Agrid[0][0]

Bgrid[0][j]

Cgrid[i][0]

Ddp[0][0]

Attempts:

3 left

💡 Hint

Common Mistakes

Using dp values on the right side instead of grid values

Mixing row and column indices incorrectly

Initialize dp[0][0] with grid[0][0], fill first row with grid[0][j], and first column with grid[i][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