Minimum Path Sum in Grid in DSA Python

Mental Model

Find the smallest total by moving only right or down from the top-left to the bottom-right of a grid.

Analogy: Imagine walking through a city grid where each block has a cost to cross. You want to reach your friend's house at the bottom-right corner by paying the least total cost, moving only east or south.

Start:
[1] -> [3] -> [1]
 ↓      ↓      ↓
[1] -> [5] -> [1]
 ↓      ↓      ↓
[4] -> [2] -> [1]

You start at top-left [1] and want to reach bottom-right [1].

Dry Run Walkthrough

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

Goal: Find the path from top-left to bottom-right with the smallest sum of numbers, moving only right or down.

Step 1: Start at top-left cell, cost is 1

[1] -> [3] -> [1]
 ↓      ↓      ↓
[1] -> [5] -> [1]
 ↓      ↓      ↓
[4] -> [2] -> [1]

Why: We begin with the starting point cost.

Step 2: Fill first row by adding costs moving right: 1+3=4, then 4+1=5

[1] -> [4] -> [5]
 ↓      ↓      ↓
[1] -> [5] -> [1]
 ↓      ↓      ↓
[4] -> [2] -> [1]

Why: Only right moves possible in first row, so accumulate sums.

Step 3: Fill first column by adding costs moving down: 1+1=2, then 2+4=6

[1] -> [4] -> [5]
 ↓      ↓      ↓
[2] -> [5] -> [1]
 ↓      ↓      ↓
[6] -> [2] -> [1]

Why: Only down moves possible in first column, so accumulate sums.

Step 4: Calculate cell (1,1): min(top=4, left=2) + 5 = 7

[1] -> [4] -> [5]
 ↓      ↓      ↓
[2] -> [7] -> [1]
 ↓      ↓      ↓
[6] -> [2] -> [1]

Why: Choose the cheaper path to reach this cell.

Step 5: Calculate cell (1,2): min(top=5, left=7) + 1 = 6

[1] -> [4] -> [5]
 ↓      ↓      ↓
[2] -> [7] -> [6]
 ↓      ↓      ↓
[6] -> [2] -> [1]

Why: Choose the cheaper path to reach this cell.

Step 6: Calculate cell (2,1): min(top=7, left=6) + 2 = 8

[1] -> [4] -> [5]
 ↓      ↓      ↓
[2] -> [7] -> [6]
 ↓      ↓      ↓
[6] -> [8] -> [1]

Why: Choose the cheaper path to reach this cell.

Step 7: Calculate cell (2,2): min(top=6, left=8) + 1 = 7

[1] -> [4] -> [5]
 ↓      ↓      ↓
[2] -> [7] -> [6]
 ↓      ↓      ↓
[6] -> [8] -> [7]

Why: Choose the cheaper path to reach the bottom-right cell.

Result:

Final grid with minimum path sums:
[1] -> [4] -> [5]
 ↓      ↓      ↓
[2] -> [7] -> [6]
 ↓      ↓      ↓
[6] -> [8] -> [7]
Minimum path sum = 7

Annotated Code

DSA Python

from typing import List

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        if not grid or not grid[0]:
            return 0
        m, n = len(grid), len(grid[0])
        # Fill first row
        for j in range(1, n):
            grid[0][j] += grid[0][j-1]  # accumulate cost moving right
        # Fill first column
        for i in range(1, m):
            grid[i][0] += grid[i-1][0]  # accumulate cost moving down
        # Fill rest of grid
        for i in range(1, m):
            for j in range(1, n):
                grid[i][j] += min(grid[i-1][j], grid[i][j-1])  # choose cheaper path
        return grid[m-1][n-1]

# Driver code
sol = Solution()
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(sol.minPathSum(grid))

for j in range(1, n): grid[0][j] += grid[0][j-1]

accumulate sums in first row moving right

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

accumulate sums in first column moving down

for i in range(1, m): for j in range(1, n): grid[i][j] += min(grid[i-1][j], grid[i][j-1])

choose minimum path sum from top or left cell

Output

7

Complexity Analysis

Time: O(m*n) because we visit each cell once to compute minimum sums

Space: O(1) because we update the grid in place without extra space

vs Alternative: Compared to recursive solutions without memoization which are exponential, this dynamic programming approach is efficient and uses constant extra space.

Edge Cases

Empty grid

Returns 0 as there is no path

DSA Python

if not grid or not grid[0]:
    return 0

Single row grid

Accumulates sums moving right only

DSA Python

for j in range(1, n):
    grid[0][j] += grid[0][j-1]

Single column grid

Accumulates sums moving down only

DSA Python

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

When to Use This Pattern

When you need to find the cheapest or shortest path in a grid moving only right or down, use the minimum path sum dynamic programming pattern to build solutions from smaller subproblems.

Common Mistakes

Mistake: Not initializing the first row and first column sums before filling the rest of the grid
Fix: Explicitly accumulate sums for the first row and first column before processing inner cells

Mistake: Using max instead of min when choosing between top and left cells
Fix: Use min to find the minimum path sum

Summary

Calculates the minimum sum path from top-left to bottom-right in a grid moving only right or down.

Use when you want the cheapest path cost in a grid with movement constraints.

Build the solution by accumulating minimum sums row-wise and column-wise, then filling the rest using the minimum of top and left neighbors.

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