Minimum Path Sum in Grid in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the goal of the Minimum Path Sum problem in a grid?

To find the path from the top-left corner to the bottom-right corner of a grid that has the smallest possible sum of the numbers along the path, moving only down or right.

beginner

Which moves are allowed when finding the minimum path sum in a grid?

Only moves to the right or moves down are allowed at each step.

intermediate

Why is dynamic programming a good approach for the Minimum Path Sum problem?

Because the problem has overlapping subproblems and optimal substructure, so we can store the minimum sums for smaller parts of the grid and reuse them to build the solution for the whole grid efficiently.

intermediate

In Rust, what data structure is commonly used to store the minimum path sums for each cell?

A 2D vector (Vec) is commonly used to store the minimum path sums for each cell in the grid.

intermediate

What is the time complexity of the dynamic programming solution for the Minimum Path Sum problem in an m x n grid?

The time complexity is O(m * n) because we compute the minimum path sum for each cell once.

In the Minimum Path Sum problem, which cell do we start from?

A Top-left corner

B Bottom-right corner

C Top-right corner

D Bottom-left corner

We start from the top-left corner and move only right or down to reach the bottom-right corner.

Which of these moves is NOT allowed in the Minimum Path Sum problem?

A Move right

B Move diagonally

C Move down

D None of the above

Only moves to the right or down are allowed; diagonal moves are not allowed.

What does the dynamic programming table store in the Minimum Path Sum problem?

A Maximum sums for each cell

B Number of paths to each cell

C Coordinates of the path

D Minimum sums for each cell

The table stores the minimum sum needed to reach each cell from the start.

What is the minimum path sum for a grid with only one cell containing the value 5?

A 1

B 0

C 5

D Undefined

The path sum is just the value of the single cell, which is 5.

If the grid size is 3x3, how many cells' minimum sums do we calculate in the dynamic programming solution?

A 9

B 6

C 3

D 12

We calculate the minimum sum for each of the 9 cells in the 3x3 grid.

Explain how you would use dynamic programming to solve the Minimum Path Sum problem in a grid.

Think about building the solution step-by-step from the start.

Describe the constraints on movement and how they affect the path choices in the Minimum Path Sum problem.

Focus on allowed directions and their impact.

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