Minimum Path Sum in Grid in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the first cell of the dp grid with the grid's first cell value.

DSA Python

dp = [[0]*len(grid[0]) for _ in range(len(grid))]
dp[0][0] = grid[1]

Drag options to blanks, or click blank then click option'

A(0,0)

B(0)(0)

C{0}{0}

D[0][0]

Attempts:

3 left

💡 Hint

Common Mistakes

Using parentheses instead of square brackets for indexing.

Trying to access grid with a tuple or other invalid syntax.

The first cell of the dp grid should be initialized with the value of the first cell in the input grid, which is accessed by grid[0][0].

2fill in blank

medium

Complete the code to fill the first row of the dp grid by accumulating sums from the left.

DSA Python

for j in range(1, len(grid[0])):
    dp[0][j] = dp[0][j-1] [1] grid[0][j]

Drag options to blanks, or click blank then click option'

A+

B-

C*

D//

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction or multiplication instead of addition.

Using integer division which truncates the sum.

We add the current grid cell value to the sum accumulated from the left to fill the first row.

3fill in blank

hard

Fix the error in the code to correctly fill the dp grid for cells not in the first row or column.

DSA Python

for i in range(1, len(grid)):
    for j in range(1, len(grid[0])):
        dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][[1]])

Drag options to blanks, or click blank then click option'

Ai-1

Bj+1

Cj-1

Di+1

Attempts:

3 left

💡 Hint

Common Mistakes

Using i-1 instead of j-1 for the left cell index.

Using indices that go out of bounds.

To find the minimum path sum to dp[i][j], we add the current grid value to the minimum of the cell above (dp[i-1][j]) and the cell to the left (dp[i][j-1]).

4fill in blank

hard

Fill both blanks to complete the code that initializes the first column of the dp grid by accumulating sums from above.

DSA Python

for i in range(1, len(grid)):
    dp[i][[1]] = dp[i-1][[2]] + grid[i][0]

Drag options to blanks, or click blank then click option'

A0

B1

Ci

Dj

Attempts:

3 left

💡 Hint

Common Mistakes

Using variable indices like i or j for the column instead of 0.

Mixing row and column indices.

The first column index is 0, so dp[i][0] is updated by adding the value from the cell above dp[i-1][0] plus the current grid value.

5fill in blank

hard

Fill all three blanks to complete the function that returns the minimum path sum from top-left to bottom-right.

DSA Python

def minPathSum(grid):
    dp = [[0]*len(grid[0]) for _ in range(len(grid))]
    dp[0][0] = grid[0][0]

    for i in range(1, len(grid)):
        dp[i][0] = dp[i-1][[1]] + grid[i][0]
    for j in range(1, len(grid[0])):
        dp[0][j] = dp[0][[2]] + grid[0][j]
    for i in range(1, len(grid)):
        for j in range(1, len(grid[0])):
            dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][[3]])
    return dp[-1][-1]

Drag options to blanks, or click blank then click option'

A0

Bj-1

Cj

Di-1

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong indices for dp accesses causing index errors.

Confusing row and column indices.

The first blank is 0 because the first column index is 0. The second blank is j-1 to accumulate sums from the left. The third blank is also j-1 to find the minimum path from the left cell.

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