Minimum Path Sum in Grid in DSA Rust - Execution Trace

Concept Flow - Minimum Path Sum in Grid

Start at top-left cell (0,0)

↓

At each cell, compute min path sum from top or left

↓

Move right or down to next cell

↓

Repeat until bottom-right cell reached

↓

Result is min path sum at bottom-right cell

We start at the top-left cell and move only right or down, computing the minimum path sum to each cell by choosing the smaller sum from the top or left neighbor until we reach the bottom-right cell.

Execution Sample

DSA Rust

let grid = vec![
  vec![1,3,1],
  vec![1,5,1],
  vec![4,2,1],
];
let result = min_path_sum(&grid);

This code calculates the minimum path sum from the top-left to bottom-right of a 3x3 grid.

Execution Table

Step	Operation	Cell (row,col)	Computed Min Sum	Source (Top/Left)	Grid State
1	Initialize start cell	(0,0)	1	Start	[[1, _, _], [_, _, _], [_, _, _]]
2	Compute cell	(0,1)	4	Left (1) + 3	[[1, 4, _], [_, _, _], [_, _, _]]
3	Compute cell	(0,2)	5	Left (4) + 1	[[1, 4, 5], [_, _, _], [_, _, _]]
4	Compute cell	(1,0)	2	Top (1) + 1	[[1, 4, 5], [2, _, _], [_, _, _]]
5	Compute cell	(1,1)	7	Min(Top 4, Left 2) + 5 = 7	[[1, 4, 5], [2, 7, _], [_, _, _]]
6	Compute cell	(1,2)	6	Min(Top 5, Left 7) + 1 = 6	[[1, 4, 5], [2, 7, 6], [_, _, _]]
7	Compute cell	(2,0)	6	Top (2) + 4	[[1, 4, 5], [2, 7, 6], [6, _, _]]
8	Compute cell	(2,1)	8	Min(Top 7, Left 6) + 2 = 8	[[1, 4, 5], [2, 7, 6], [6, 8, _]]
9	Compute cell	(2,2)	7	Min(Top 6, Left 8) + 1 = 7	[[1, 4, 5], [2, 7, 6], [6, 8, 7]]
10	Return result	(2,2)	7	Bottom-right cell min path sum	[[1, 4, 5], [2, 7, 6], [6, 8, 7]]

💡 Reached bottom-right cell (2,2), minimum path sum is 7

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	Final
grid	[[1,3,1],[1,5,1],[4,2,1]]	[[1,3,1],[1,5,1],[4,2,1]]	[[1,3,1],[1,5,1],[4,2,1]]	[[1,3,1],[1,5,1],[4,2,1]]	[[1,3,1],[1,5,1],[4,2,1]]	[[1,3,1],[1,5,1],[4,2,1]]	[[1,3,1],[1,5,1],[4,2,1]]	[[1,3,1],[1,5,1],[4,2,1]]	[[1,3,1],[1,5,1],[4,2,1]]	[[1,3,1],[1,5,1],[4,2,1]]	[[1,3,1],[1,5,1],[4,2,1]]
dp	[empty]	[[1,_,_],[_,_,_],[_,_,_]]	[[1,4,_],[_,_,_],[_,_,_]]	[[1,4,5],[_,_,_],[_,_,_]]	[[1,4,5],[2,_,_],[_,_,_]]	[[1,4,5],[2,7,_],[_,_,_]]	[[1,4,5],[2,7,6],[_,_,_]]	[[1,4,5],[2,7,6],[6,_,_]]	[[1,4,5],[2,7,6],[6,8,_]]	[[1,4,5],[2,7,6],[6,8,7]]	[[1,4,5],[2,7,6],[6,8,7]]

Key Moments - 3 Insights

Why do we only consider the top and left cells when computing the minimum path sum for a cell?

Because the problem allows movement only down or right, the minimum path to a cell can only come from the cell above (top) or the cell to the left. This is shown in the execution_table rows 2-9 where each cell's min sum depends on top or left neighbors.

Why is the starting cell's minimum path sum equal to its own value?

The starting cell (0,0) has no cells above or to the left, so its minimum path sum is just its own value. This is shown in execution_table row 1.

How do we handle the first row and first column differently?

For the first row, we can only come from the left, so sums accumulate by adding left cells. For the first column, we can only come from above, so sums accumulate by adding top cells. This is visible in execution_table rows 2,3 (first row) and 4,7 (first column).

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the computed minimum path sum for cell (1,1)?

A 5

B 6

C 7

D 8

💡 Hint

Check the 'Computed Min Sum' column at step 5 in the execution_table.

At which step does the minimum path sum for cell (2,2) get computed?

A Step 8

B Step 9

C Step 7

D Step 10

💡 Hint

Look for the row where 'Cell (row,col)' is (2,2) and 'Operation' is 'Compute cell' in the execution_table.

If the value at grid cell (1,1) changed from 5 to 2, how would the minimum path sum at cell (2,2) change?

A It would decrease

B It would increase

C It would stay the same

D It would become zero

💡 Hint

Consider how the minimum path sums depend on neighboring cells' values as shown in the execution_table and variable_tracker.

Concept Snapshot

Minimum Path Sum in Grid:
- Start at top-left cell
- Move only right or down
- At each cell, min path sum = cell value + min(top cell sum, left cell sum)
- First row and column sums accumulate from one direction
- Result is min path sum at bottom-right cell

Full Transcript

The minimum path sum in a grid is found by starting at the top-left cell and moving only right or down to reach the bottom-right cell. At each cell, we calculate the minimum path sum by adding the cell's value to the smaller of the sums from the cell above or to the left. The first row and first column are special cases where only one direction is possible. We track these sums in a dp structure until we reach the bottom-right cell, which holds the final minimum path sum. This process is shown step-by-step in the execution table and variable tracker.

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