Minimum Path Sum in Grid in DSA Java - Execution Trace

Concept Flow - Minimum Path Sum in Grid

Start at top-left cell (0,0)

↓

Check if at bottom-right cell?

Yes→Return current sum

No↓

Move Right or Down

↓

Add cell value

↓

Choose min path sum

↓

Repeat until bottom-right reached

Start from the top-left cell, move only right or down, add cell values, and choose the path with the smallest sum until reaching the bottom-right cell.

Execution Sample

DSA Java

int minPathSum(int[][] grid) {
  int m = grid.length, n = grid[0].length;
  int[][] dp = new int[m][n];
  dp[0][0] = grid[0][0];
  // fill dp
  return dp[m-1][n-1];
}

Calculates the minimum path sum from top-left to bottom-right in a grid by dynamic programming.

Execution Table

Step	Operation	Cell (i,j)	dp[i][j] Value	Calculation	Grid State Visual
1	Initialize dp[0][0]	(0,0)	1	dp[0][0] = grid[0][0] = 1	[1, _, _] [_, _, _] [_, _, _]
2	Fill first row	(0,1)	4	dp[0][1] = dp[0][0] + grid[0][1] = 1 + 3	[1, 4, _] [_, _, _] [_, _, _]
3	Fill first row	(0,2)	5	dp[0][2] = dp[0][1] + grid[0][2] = 4 + 1	[1, 4, 5] [_, _, _] [_, _, _]
4	Fill first column	(1,0)	4	dp[1][0] = dp[0][0] + grid[1][0] = 1 + 3	[1, 4, 5] [4, _, _] [_, _, _]
5	Calculate dp[1][1]	(1,1)	8	min(dp[0][1], dp[1][0]) + grid[1][1] = min(4,4)+4=8	[1, 4, 5] [4, 8, _] [_, _, _]
6	Calculate dp[1][2]	(1,2)	9	min(dp[0][2], dp[1][1]) + grid[1][2] = min(5,8)+4=9	[1, 4, 5] [4, 8, 9] [_, _, _]
7	Fill first column	(2,0)	7	dp[2][0] = dp[1][0] + grid[2][0] = 4 + 3	[1, 4, 5] [4, 8, 9] [7, _, _]
8	Calculate dp[2][1]	(2,1)	9	min(dp[1][1], dp[2][0]) + grid[2][1] = min(8,7)+2=9	[1, 4, 5] [4, 8, 9] [7, 9, _]
9	Calculate dp[2][2]	(2,2)	11	min(dp[1][2], dp[2][1]) + grid[2][2] = min(9,9)+2=11	[1, 4, 5] [4, 8, 9] [7, 9, 11]
10	Return result	(2,2)	11	Minimum path sum found at bottom-right cell	[1, 4, 5] [4, 8, 9] [7, 9, 11]

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

Variable Tracker

Variable	Start	After Step 1	After Step 5	After Step 9	Final
dp	[[_,_,_],[_,_,_],[_,_,_]]	[[1,_,_],[_,_,_],[_,_,_]]	[[1,4,5],[4,8,_],[_,_,_]]	[[1,4,5],[4,8,9],[7,9,11]]	[[1,4,5],[4,8,9],[7,9,11]]
i	0	0	1	2	2
j	0	0	1	2	2

Key Moments - 3 Insights

Why do we fill the first row and first column separately before the rest?

Because the first row and column can only be reached from one direction (left for row, top for column), so their dp values are cumulative sums. This is shown in steps 2,3 for the first row and steps 4,7 for the first column in the execution_table.

Why do we take the minimum of dp[i-1][j] and dp[i][j-1] when filling dp[i][j]?

Because we can only move right or down, so the minimum path sum to cell (i,j) depends on the minimum path sums to the cell above (i-1,j) and to the left (i,j-1). This is shown in steps 5,6,8,9 where min is used.

Why is the final answer at dp[m-1][n-1]?

Because dp[m-1][n-1] stores the minimum path sum to reach the bottom-right cell from the top-left, as shown in step 10.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of dp[1][1] at step 5?

A 8

B 9

C 4

D 7

💡 Hint

Check the row with Step 5 in the execution_table under 'dp[i][j] Value'

At which step does the dp value for cell (2,2) get calculated?

A Step 7

B Step 9

C Step 6

D Step 10

💡 Hint

Look for the row where Cell (2,2) is mentioned in the execution_table

If the grid value at (1,1) changed from 4 to 1, how would dp[1][1] change at step 5?

A It would remain 8

B It would become 4

C It would become 5

D It would become 9

💡 Hint

Recall dp[1][1] = min(dp[0][1], dp[1][0]) + grid[1][1], check values at step 5

Concept Snapshot

Minimum Path Sum in Grid:
- Use dp array same size as grid
- dp[0][0] = grid[0][0]
- Fill first row and column cumulatively
- For other cells: dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
- Result at dp[m-1][n-1]

Full Transcript

This visualization traces the minimum path sum calculation in a grid using dynamic programming. We start at the top-left cell and fill a dp array with minimum sums to reach each cell. First, the dp array's first row and column are filled cumulatively because movement is restricted to right and down. Then, for each other cell, we take the minimum of the top and left dp values plus the current grid cell value. The final answer is found at the bottom-right cell of the dp array. The execution table shows each step with the dp value updates and the grid state. Key moments clarify why the first row and column are handled separately and why the minimum of two neighbors is chosen. The visual quiz tests understanding of dp values at specific steps and the effect of changing grid values.

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 smallest sum of numbers from top-left to bottom-right

B. The path with the largest sum of numbers from top-left to bottom-right

C. The number of paths from top-left to bottom-right

D. The maximum number in the grid

Solution

1. Step 1: Understand the problem goal

   The problem asks to find a path from the top-left cell to the bottom-right cell of a grid such that the sum of all numbers on the path is as small as possible.

2. Step 2: Clarify path movement

   Movement is only allowed down or right at each step, so the path is constrained.

3. Final Answer:

   The path with the smallest sum of numbers from top-left to bottom-right -> Option A

4. Quick Check:

   Minimum path sum means smallest total sum [OK]

Hint: Look for smallest sum path moving only right or down [OK]

Common Mistakes:

• Thinking the path can move diagonally or up
• Looking for maximum sum instead of minimum
• Counting number of paths instead of sum

2. Which of the following Java code snippets correctly initializes a 2D array named grid with 3 rows and 3 columns filled with zeros?

easy

A. int grid[][] = new int[3];

B. int[][] grid = new int[3][3];

C. int[] grid = new int[3][3];

D. int[][] grid = new int[3];

Solution

1. Step 1: Understand Java 2D array syntax

   In Java, a 2D array is declared as int[][] name = new int[rows][columns];. This creates a grid with specified rows and columns.

2. Step 2: Check each option

   int[][] grid = new int[3][3]; correctly declares a 3x3 int 2D array. Options A, C, and D have incorrect syntax or dimensions.

3. Final Answer:

   int[][] grid = new int[3][3]; -> Option B

4. Quick Check:

   Correct 2D array syntax = int[][] grid = new int[3][3]; [OK]

Hint: Use int[][] name = new int[rows][cols] for 2D arrays [OK]

Common Mistakes:

• Declaring 2D arrays with wrong brackets
• Initializing only one dimension
• Confusing 1D and 2D array syntax

3. What is the output of the following Java code that calculates the minimum path sum in a 2x2 grid?

int[][] grid = {{1, 3}, {1, 5}};
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = grid[0][0];
for (int i = 1; i < m; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
for (int j = 1; j < n; j++) dp[0][j] = dp[0][j-1] + grid[0][j];
for (int i = 1; i < m; i++) {
  for (int j = 1; j < n; j++) {
    dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
  }
}
System.out.println(dp[m-1][n-1]);

medium

A. 7

B. 8

C. 9

D. 10

Solution

1. Step 1: Initialize dp array with first row and column sums

   dp[0][0] = 1
   dp[1][0] = dp[0][0] + grid[1][0] = 1 + 1 = 2
   dp[0][1] = dp[0][0] + grid[0][1] = 1 + 3 = 4

2. Step 2: Calculate dp[1][1]

   dp[1][1] = min(dp[0][1], dp[1][0]) + grid[1][1] = min(4, 2) + 5 = 2 + 5 = 7

3. Final Answer:

   7 -> Option A

4. Quick Check:

   Minimum path sum = 7 [OK]

Hint: Fill dp row and column first, then use min of top and left [OK]

Common Mistakes:

• Adding max instead of min
• Not initializing first row and column correctly
• Mixing indices in loops

4. Identify the error in the following Java code snippet that tries to compute the minimum path sum in a grid:

int[][] grid = {{1,2,3},{4,5,6}};
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = grid[0][0];
for (int i = 1; i < m; i++) {
  dp[i][0] = dp[i-1][0] + grid[i][0];
}
for (int j = 1; j < n; j++) {
  dp[0][j] = dp[0][j-1] + grid[0][j];
}
for (int i = 1; i < m; i++) {
  for (int j = 1; j < n; j++) {
    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + grid[i][j];
  }
}

medium

A. Grid dimensions are wrong

B. Not initializing dp[0][0]

C. Loop ranges are incorrect

D. Using Math.max instead of Math.min in dp calculation

Solution

1. Step 1: Check dp initialization

   dp[0][0] is correctly initialized to grid[0][0]. Loops for first row and column are correct.

2. Step 2: Identify the error in dp update

   The inner loop uses Math.max instead of Math.min, which finds the maximum path sum, not minimum.

3. Final Answer:

   Using Math.max instead of Math.min in dp calculation -> Option D

4. Quick Check:

   Minimum path sum needs Math.min, not Math.max [OK]

Hint: Use Math.min to find minimum path sum, not Math.max [OK]

Common Mistakes:

• Using max instead of min in dp update
• Forgetting to initialize dp[0][0]
• Incorrect loop boundaries

5. Given a 3x3 grid:

int[][] grid = {
  {1, 2, 5},
  {3, 2, 1},
  {4, 1, 1}
};

What is the minimum path sum from top-left to bottom-right moving only right or down?

hard

A. 9

B. 8

C. 7

D. 10

Solution

1. Step 1: Initialize dp first row and column sums

   dp[0][0] = 1
   dp[0][1] = 1 + 2 = 3
   dp[0][2] = 3 + 5 = 8
   dp[1][0] = 1 + 3 = 4
   dp[2][0] = 4 + 4 = 8

2. Step 2: Calculate dp values for inner cells

   dp[1][1] = min(dp[0][1], dp[1][0]) + 2 = min(3,4) + 2 = 5
   dp[1][2] = min(dp[0][2], dp[1][1]) + 1 = min(8,5) + 1 = 6
   dp[2][1] = min(dp[1][1], dp[2][0]) + 1 = min(5,8) + 1 = 6
   dp[2][2] = min(dp[1][2], dp[2][1]) + 1 = min(6,6) + 1 = 7

3. Final Answer:

   7 -> Option C

4. Quick Check:

   Minimum path sum = 7 [OK]

Hint: Fill dp row and column first, then inner cells with min of top and left [OK]

Common Mistakes:

• Not updating dp correctly for inner cells
• Adding max instead of min
• Incorrect initialization of first row or column