Minimum Path Sum in Grid in DSA Typescript - Execution Trace

Concept Flow - Minimum Path Sum in Grid

Start at top-left cell (0,0)

↓

Calculate min path sum for current cell

↓

Move right or down

↓

Right cell

↓

Choose smaller sum + current cell value

↓

Repeat until bottom-right cell reached

↓

Return min path sum at bottom-right

Start from the top-left cell, move only right or down, calculate minimum path sums step-by-step until reaching the bottom-right cell.

Execution Sample

DSA Typescript

function minPathSum(grid: number[][]): number {
  const m = grid.length, n = grid[0].length;
  for (let i = 1; i < m; i++) grid[i][0] += grid[i-1][0];
  for (let j = 1; j < n; j++) grid[0][j] += grid[0][j-1];
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);
    }
  }
  return grid[m-1][n-1];
}

Calculates minimum path sum from top-left to bottom-right by updating grid cells with cumulative minimum sums.

Execution Table

Step	Operation	Cell Updated	Value Added	Grid State	Explanation
1	Initialize first column	(1,0)	1 + 3 = 4	[[1,3,1],[4,5,1],[1,5,1]]	Add above cell value to current cell in first column
2	Initialize first column	(2,0)	4 + 1 = 5	[[1,3,1],[4,5,1],[5,5,1]]	Add above cell value to current cell in first column
3	Initialize first row	(0,1)	1 + 3 = 4	[[1,4,1],[4,5,1],[5,5,1]]	Add left cell value to current cell in first row
4	Initialize first row	(0,2)	4 + 1 = 5	[[1,4,5],[4,5,1],[5,5,1]]	Add left cell value to current cell in first row
5	Update cell	(1,1)	5 + min(4,4) = 9	[[1,4,5],[4,9,1],[5,5,1]]	Add min of top and left cells to current cell
6	Update cell	(1,2)	1 + min(5,9) = 6	[[1,4,5],[4,9,6],[5,5,1]]	Add min of top and left cells to current cell
7	Update cell	(2,1)	5 + min(9,5) = 10	[[1,4,5],[4,9,6],[5,10,1]]	Add min of top and left cells to current cell
8	Update cell	(2,2)	1 + min(6,10) = 7	[[1,4,5],[4,9,6],[5,10,7]]	Add min of top and left cells to current cell
9	Return result	(2,2)	7	[[1,4,5],[4,9,6],[5,10,7]]	Minimum path sum is value at bottom-right cell

💡 Reached bottom-right cell (2,2), minimum path sum calculated as 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	Final
grid	[[1,3,1],[1,5,1],[4,2,1]]	[[1,3,1],[4,5,1],[4,2,1]]	[[1,3,1],[4,5,1],[5,2,1]]	[[1,4,1],[4,5,1],[5,2,1]]	[[1,4,5],[4,5,1],[5,2,1]]	[[1,4,5],[4,9,1],[5,2,1]]	[[1,4,5],[4,9,6],[5,2,1]]	[[1,4,5],[4,9,6],[5,10,1]]	[[1,4,5],[4,9,6],[5,10,7]]	[[1,4,5],[4,9,6],[5,10,7]]

Key Moments - 3 Insights

Why do we first update the first row and first column separately before the rest of the grid?

Because the first row and column can only be reached from one direction (left for row, top for column), so their minimum path sums are cumulative sums along that row or column. This is shown in steps 1-4 in the execution_table.

Why do we add the minimum of the top and left cells to the current cell value?

Because the path to the current cell can only come from the top or left, so we choose the smaller path sum to ensure the minimum total. This is shown in steps 5-8 in the execution_table.

Why is the final answer the value at the bottom-right cell?

Because after updating all cells with minimum path sums, the bottom-right cell contains the minimum sum to reach it from the top-left, as shown in step 9.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of the grid at cell (1,1) after step 5?

A 9

B 5

C 6

D 4

💡 Hint

Check the 'Cell Updated' and 'Value Added' columns in step 5 of the execution_table.

At which step does the condition to update the bottom-right cell (2,2) happen?

A Step 7

B Step 8

C Step 9

D Step 6

💡 Hint

Look for the step where cell (2,2) is updated in the execution_table.

If the initial grid's first row was [1,1,1] instead of [1,3,1], how would the value at cell (0,2) after step 4 change?

A It would be 3

B It would be 2

C It would be 1

D It would be 4

💡 Hint

Refer to the variable_tracker and execution_table steps 3 and 4 for first row initialization.

Concept Snapshot

Minimum Path Sum in Grid:
- Start at top-left cell
- Initialize first row and column with cumulative sums
- For each cell, add min(top, left) cell value
- Move only right or down
- Result is value at bottom-right cell

Full Transcript

This visualization shows how to find the minimum path sum in a grid by moving only right or down. We start at the top-left cell and update the first row and first column with cumulative sums because they have only one path. Then, for each other cell, we add the minimum of the top and left cells to the current cell's value. This process continues until we reach the bottom-right cell, which holds the minimum path sum. The execution table tracks each update step, showing the cell updated, the value added, and the grid state after each operation. Key moments clarify why we initialize the first row and column separately and why we choose the minimum of the top and left cells. The visual quiz tests understanding of specific steps and changes in the grid values.