Minimum Path Sum in Grid in DSA Python - 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 path sum

No↓

Move Right or Down

↓

Add cell value to path sum

↓

Repeat until bottom-right reached

Start from the top-left cell, move only right or down, add cell values, and find the path with the smallest sum to reach the bottom-right cell.

Execution Sample

DSA Python

grid = [[1,3,1],
        [1,5,1],
        [4,2,1]]

# Find minimum path sum from top-left to bottom-right
# Moves allowed: right or down only

This code finds the minimum sum path from the top-left to bottom-right in a 3x3 grid moving only right or down.

Execution Table

Step	Operation	Current Cell (row,col)	Path Sum at Cell	Action	Visual State (Grid with sums)
1	Initialize	(0,0)	1	Start at top-left	[[1, _, _], [_, _, _], [_, _, _]]
2	Fill first row	(0,1)	4	Add left cell sum + current cell value (1+3)	[[1, 4, _], [_, _, _], [_, _, _]]
3	Fill first row	(0,2)	5	Add left cell sum + current cell value (4+1)	[[1, 4, 5], [_, _, _], [_, _, _]]
4	Fill first column	(1,0)	2	Add top cell sum + current cell value (1+1)	[[1, 4, 5], [2, _, _], [_, _, _]]
5	Fill first column	(2,0)	6	Add top cell sum + current cell value (2+4)	[[1, 4, 5], [2, _, _], [6, _, _]]
6	Fill cell	(1,1)	7	Min(top=4, left=2) + current cell (5) = 2+5=7	[[1, 4, 5], [2, 7, _], [6, _, _]]
7	Fill cell	(1,2)	6	Min(top=5, left=7) + current cell (1) = 5+1=6 but left=7+1=8, choose 6	[[1, 4, 5], [2, 7, 6], [6, _, _]]
8	Fill cell	(2,1)	8	Min(top=7, left=6) + current cell (2) = 6+2=8	[[1, 4, 5], [2, 7, 6], [6, 8, _]]
9	Fill cell	(2,2)	7	Min(top=6, left=8) + current cell (1) = 6+1=7	[[1, 4, 5], [2, 7, 6], [6, 8, 7]]
10	Result	(2,2)	7	Minimum path sum found at bottom-right	[[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 2	After Step 4	After Step 6	After Step 9	Final
row	0	0	1	1	2	2
col	0	1	0	1	2	2
path_sum_grid	[[1,_,_],[_,_,_],[_,_,_]]	[[1,4,_],[_,_,_],[_,_,_]]	[[1,4,5],[2,_,_],[_,_,_]]	[[1,4,5],[2,7,_],[6,_,_]]	[[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 fill the first row and first column separately before filling other cells?

Because the first row cells can only be reached from the left and the first column cells only from above, so their path sums are cumulative sums along that row or column. This is shown in steps 2, 3 (first row) and 4, 5 (first column) in the execution_table.

How do we decide which path sum to use when filling a cell not in the first row or column?

We take the minimum of the path sums from the cell above and the cell to the left, then add the current cell's value. For example, at step 6, cell (1,1) uses min(4,2)+5=7 as shown in the execution_table.

How is the minimum path sum of 7 calculated at the bottom-right cell?

At step 9, it is min(top=6, left=8) + current cell (1) = 7, as shown in the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the path sum at cell (1,1)?

A 7

B 9

C 5

D 6

💡 Hint

Check the 'Path Sum at Cell' column for step 6 in the execution_table.

At which step does the algorithm finish filling the last cell (2,2)?

A Step 8

B Step 9

C Step 10

D Step 7

💡 Hint

Look for the step where Current Cell is (2,2) in the execution_table.

If the value at cell (1,2) changed from 1 to 10, how would the path sum at (1,2) change at step 7?

A It would increase to 15

B It would remain 6

C It would decrease to 5

D It would become 7

💡 Hint

At step 7, path sum at (1,2) = min(top=5, left=7) + current cell value; changing current cell value affects this sum.

Concept Snapshot

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

Full Transcript

The Minimum Path Sum in Grid problem finds the smallest sum of values from the top-left to the bottom-right cell, moving only right or down. We start by initializing the top-left cell with its own value. Then, we fill the first row and first column by adding the current cell's value to the sum of the previous cell in the same row or column. For other cells, we take the minimum path sum from the cell above or to the left and add the current cell's value. This process continues until we reach the bottom-right cell, which holds the minimum path sum. The execution table shows each step with the current cell, path sums, and the grid state. Key moments clarify why the first row and column are filled separately and how the minimum is chosen for other cells. The visual quiz tests understanding of path sums at specific steps and the effect of changing cell 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. Which best describes the path allowed?

easy

A. Only moves left or up at each step

B. Moves in any direction including diagonals

C. Only moves right or down at each step

D. Moves randomly without restrictions

Solution

1. Step 1: Understand the problem constraints

   The problem states you can only move right or down from each cell in the grid.

2. Step 2: Identify the path type

   This means the path is restricted to moves that go either to the right or downward, no other directions allowed.

3. Final Answer:

   Only moves right or down at each step -> Option C

4. Quick Check:

   Allowed moves = right or down [OK]

Hint: Remember: path moves only right or down [OK]

Common Mistakes:

• Thinking diagonal moves are allowed
• Assuming moves can go left or up
• Ignoring movement restrictions

2. Which of the following Python code snippets correctly initializes a 2D list named dp with zeros for a grid of size m rows and n columns?

easy

A. dp = [[0]*m for _ in range(n)]

B. dp = [[0]*n for _ in range(m)]

C. dp = [[0]*n]*m

D. dp = [0]*m*n

Solution

1. Step 1: Understand 2D list initialization

   We want a list with m rows and n columns, so outer list length is m, inner list length is n.

2. Step 2: Check each option

   dp = [[0]*n for _ in range(m)] uses list comprehension to create m separate lists each of length n filled with 0, which is correct. dp = [[0]*m for _ in range(n)] swaps m and n. dp = [[0]*n]*m creates shallow copies causing shared inner lists. dp = [0]*m*n creates a flat list, not 2D.

3. Final Answer:

   dp = [[0]*n for _ in range(m)] -> Option B

4. Quick Check:

   Correct 2D zero list = [[0]*n for _ in range(m)] [OK]

Hint: Use list comprehension for independent inner lists [OK]

Common Mistakes:

• Using [[0]*n]*m causing shared references
• Swapping m and n dimensions
• Creating a flat list instead of 2D

3. What is the output of the following code?

grid = [[1,3,1],[1,5,1],[4,2,1]]
dp = [[0]*3 for _ in range(3)]
dp[0][0] = grid[0][0]
for i in range(1,3):
    dp[0][i] = dp[0][i-1] + grid[0][i]
for j in range(1,3):
    dp[j][0] = dp[j-1][0] + grid[j][0]
for i in range(1,3):
    for j in range(1,3):
        dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
print(dp[2][2])

medium

A. 9

B. 8

C. 10

D. 7

Solution

1. Step 1: Fill first row and column of dp

   dp[0][0]=1; dp[0][1]=1+3=4; dp[0][2]=4+1=5; dp[1][0]=1+1=2; dp[2][0]=2+4=6

2. Step 2: Calculate dp values for inner cells

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

3. Final Answer:

   7 -> Option D

4. Quick Check:

   Minimum path sum = 7 [OK]

Hint: Fill dp row and column first, then inner cells [OK]

Common Mistakes:

• Mixing up indices i and j
• Adding instead of taking minimum
• Incorrect initialization of dp

4. Find the error in this code snippet for minimum path sum:

def minPathSum(grid):
    m, n = len(grid), len(grid[0])
    dp = [[0]*n]*m
    dp[0][0] = grid[0][0]
    for i in range(1, m):
        dp[i][0] = dp[i-1][0] + grid[i][0]
    for j in range(1, n):
        dp[0][j] = dp[0][j-1] + grid[0][j]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
    return dp[m-1][n-1]

medium

A. dp initialization uses shallow copy causing wrong updates

B. Loops start from 0 instead of 1

C. Return statement returns wrong cell

D. grid dimensions are swapped

Solution

1. Step 1: Analyze dp initialization

   dp = [[0]*n]*m creates m references to the same inner list, so updating one row updates all rows.

2. Step 2: Consequence of shallow copy

   When dp[i][0] or dp[0][j] is updated, all rows change, causing incorrect path sums.

3. Final Answer:

   dp initialization uses shallow copy causing wrong updates -> Option A

4. Quick Check:

   Use list comprehension for dp initialization [OK]

Hint: Avoid [[0]*n]*m; use list comprehension instead [OK]

Common Mistakes:

• Using shallow copy for 2D lists
• Incorrect loop ranges
• Returning wrong dp cell

5. Given a grid:

grid = [[2,1,3],[6,5,4],[7,8,9]]

Write a function to find the minimum path sum from top-left to bottom-right moving only right or down. What is the minimum path sum?

hard

A. 19

B. 21

C. 20

D. 18

Solution

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

   dp[0][0]=2; first row: dp[0][1]=2+1=3, dp[0][2]=3+3=6; first column: dp[1][0]=2+6=8, dp[2][0]=8+7=15

2. Step 2: Fill remaining dp cells

   dp[1][1]=min(dp[0][1],dp[1][0])+5=min(3,8)+5=8; dp[1][2]=min(dp[0][2],dp[1][1])+4=min(6,8)+4=10; dp[2][1]=min(dp[1][1],dp[2][0])+8=min(8,15)+8=16; dp[2][2]=min(dp[1][2],dp[2][1])+9=min(10,16)+9=19

3. Final Answer:

   19 -> Option A

4. Quick Check:

   Minimum path sum = 19 [OK]

Hint: Calculate dp row and column first, then inner cells [OK]

Common Mistakes:

• Incorrect dp initialization
• Mixing up indices in loops
• Adding max instead of min