Minimum Path Sum in Grid in DSA Python - Build from Scratch

Minimum Path Sum in Grid

📖 Scenario: Imagine you are helping a delivery robot find the easiest path through a city grid. Each block in the city has a cost representing how hard it is to cross. The robot can only move right or down. Your job is to help the robot find the path with the smallest total cost from the top-left corner to the bottom-right corner.

🎯 Goal: Build a program that calculates the minimum path sum in a grid of costs, moving only right or down.

📋 What You'll Learn

Create a 2D list called grid with exact values

Create a variable called rows to store the number of rows in grid

Use nested for loops with variables r and c to update grid with minimum path sums

Print the minimum path sum found at the bottom-right corner of grid

💡 Why This Matters

🌍 Real World

Finding the easiest or cheapest path through a grid is useful in robotics, GPS navigation, and game development.

💼 Career

Understanding grid-based pathfinding and dynamic programming is important for software engineers working on algorithms, AI, and optimization problems.

1

Create the grid of costs

Create a 2D list called grid with these exact values: [[1, 3, 1], [1, 5, 1], [4, 2, 1]]

DSA Python

# Create the grid of costs
# Your code here

Hint

Use square brackets to create a list of lists with the exact numbers.

2

Get the number of rows in the grid

Create a variable called rows and set it to the number of rows in grid using len(grid)

DSA Python

grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
# Create variable rows to store number of rows
# Your code here

Hint

Use the len() function to find how many lists are inside grid.

3

Calculate minimum path sums in the grid

Use nested for loops with variables r and c to update grid so each cell contains the minimum path sum to reach it. Skip the top-left cell. For the first row, add the value from the left cell. For the first column, add the value from the above cell. For other cells, add the minimum of the top or left cell values.

DSA Python

grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
rows = len(grid)
# Use nested for loops with r and c to update grid with minimum path sums
# Your code here

Hint

Remember to handle the first row and first column separately because they only have one direction to come from.

4

Print the minimum path sum

Print the value at the bottom-right corner of grid using print(grid[rows-1][len(grid[0])-1])

DSA Python

grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
rows = len(grid)
cols = len(grid[0])
for r in range(rows):
    for c in range(cols):
        if r == 0 and c == 0:
            continue
        elif r == 0:
            grid[r][c] += grid[r][c-1]
        elif c == 0:
            grid[r][c] += grid[r-1][c]
        else:
            grid[r][c] += min(grid[r-1][c], grid[r][c-1])
# Print the minimum path sum
# Your code here

Hint

The minimum path sum is stored in the bottom-right cell of the grid after updating.

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