LeetCode 64: Minimum Path Sum Solution in Python Explained

Problem Statement

LeetCode 64, Minimum Path Sum, is a medium-level problem where you’re given an (m \times n) grid filled with non-negative integers grid. Your task is to find a path from the top-left corner (0,0) to the bottom-right corner (m-1,n-1) that minimizes the sum of all numbers along the path, moving only right or down. Return the minimum path sum as an integer.

Constraints

1 <= m, n <= 200: Grid dimensions are between 1 and 200.
0 <= grid[i][j] <= 200: Each cell value is between 0 and 200.

Example

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Path 1->1->1->1->1->2->1 sums to 7:
1→3  1
↓   ↓
1  5  1
↓   ↓
4  2→1

Input: grid = [[1,2,3],[4,5,6]]
Output: 12
Explanation: Path 1->2->3->6 sums to 12.

Input: grid = [[1]]
Output: 1
Explanation: Single cell path sums to 1.

Understanding the Problem

How do you solve LeetCode 64: Minimum Path Sum in Python? For grid = [[1,3,1],[1,5,1],[4,2,1]], find the path from (0,0) to (2,2) with the smallest sum—here, it’s 7 via [1,1,1,1,1,2,1]. We can only move right or down, so we need an efficient way to compute the minimum sum. We’ll explore two approaches: a Dynamic Programming Solution (optimal and primary) and an Alternative with Space-Optimized DP (more memory-efficient). The DP method runs in O(m * n) time with O(m * n) space.

Solution 1: Dynamic Programming Approach (Primary)

Explanation

Use a 2D DP table where dp[i][j] represents the minimum path sum to reach position (i,j) from (0,0). Each cell’s value is the grid value plus the minimum of the sums from above (dp[i-1][j]) or left (dp[i][j-1]). Initialize the first row and column by accumulating grid values, then fill the table.

Here’s a flow for [[1,3,1],[1,5,1],[4,2,1]]:

DP table:
[1,4,5]    [1,4,5]
[2,0,0] -> [2,7,6]
[6,0,0]    [6,8,7]
Result: dp[2][2] = 7

Initialize DP Table.

Create \(m \times n\) table, set first cell to grid[0][0].

Fill First Row and Column.

Accumulate sums along edges.

Fill Table.

For each cell, take min of above and left, add grid value.

Return Result.

Value at dp[m-1][n-1].

Step-by-Step Example

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

We need 7.

Goal: Find minimum path sum in 3x3 grid.
Result for Reference: 7.
Start: m = 3, n = 3, dp = [[0,0,0],[0,0,0],[0,0,0]].
Step 1: Initialize first cell.

dp[0][0] = grid[0][0] = 1.

Step 2: Fill first row.

dp[0][1] = dp[0][0] + 3 = 4.
dp[0][2] = dp[0][1] + 1 = 5.
dp[0] = [1,4,5].

Step 3: Fill first column.

dp[1][0] = dp[0][0] + 1 = 2.
dp[2][0] = dp[1][0] + 4 = 6.
dp = [[1,4,5],[2,0,0],[6,0,0]].

Step 4: Fill table.

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

Finish: Return dp[2][2] = 7.

Example 2: grid = [[1,2,3],[4,5,6]]

We need 12.

Start: dp = [[0,0,0],[0,0,0]].
Step 1: dp[0][0] = 1.
Step 2: First row: dp[0][1] = 3, dp[0][2] = 6.
Step 3: First column: dp[1][0] = 5.
Step 4: Fill.

dp[1][1] = min(5,3) + 5 = 8.
dp[1][2] = min(8,6) + 6 = 12.
dp = [[1,3,6],[5,8,12]].

Finish: Return dp[1][2] = 12.

How the Code Works (Dynamic Programming)

Here’s the Python code with line-by-line explanation:

def minPathSum(grid: list[list[int]]) -> int:
    # Line 1: Get dimensions
    m, n = len(grid), len(grid[0])

    # Line 2: Initialize DP table
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = grid[0][0]

    # Line 3: Fill first row
    for j in range(1, n):
        dp[0][j] = dp[0][j-1] + grid[0][j]

    # Line 4: Fill first column
    for i in range(1, m):
        dp[i][0] = dp[i-1][0] + grid[i][0]

    # Line 5: Fill rest of table
    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]

    # Line 6: Return minimum path sum
    return dp[m-1][n-1]

Alternative: Space-Optimized DP Approach

Explanation

Optimize space by using a 1D DP array, updating it row by row. Each cell dp[j] represents the minimum path sum to (i,j), needing only the current row and previous row’s values, reducing space to O(n).

Initialize 1D DP.

Size \(n\), set first row sums.

Process Rows.

Update array, taking min from above or left.

Return Result.

Last element of array.

Step-by-Step Example (Alternative)

For [[1,3,1],[1,5,1],[4,2,1]]:

Start: dp = [1,0,0].
Step 1: First row: dp = [1,4,5].
Step 2: Second row.

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

Step 3: Third row.

dp[0] = 6, dp[1] = min(6,7) + 2 = 8, dp[2] = min(8,6) + 1 = 7.

Finish: Return dp[2] = 7.

How the Code Works (Space-Optimized DP)

def minPathSumOpt(grid: list[list[int]]) -> int:
    # Line 1: Get dimensions
    m, n = len(grid), len(grid[0])

    # Line 2: Initialize 1D DP array
    dp = [float('inf')] * n
    dp[0] = 0

    # Line 3: Process each row
    for i in range(m):
        dp[0] = dp[0] + grid[i][0]  # First column
        for j in range(1, n):
            dp[j] = min(dp[j], dp[j-1]) + grid[i][j]

    # Line 4: Return minimum path sum
    return dp[n-1]

Complexity

Dynamic Programming:

Time: O(m * n) – Fill \(m \times n\) table.
Space: O(m * n) – Store DP table.

Space-Optimized DP:

Time: O(m * n) – Process each cell.
Space: O(n) – 1D array.

Efficiency Notes

Space-Optimized DP is O(m * n) time and O(n) space, more memory-efficient than the full DP’s O(m * n) space, making it a strong choice for LeetCode 64. Both are O(m * n) time, fitting the problem’s constraints.

Key Insights

Tips to master LeetCode 64:

Min Path: Take minimum of above or left at each step.
Grid Addition: Add current cell value to path sum.
Space Trick: Use 1D array to save memory.

Additional Example

For grid = [[1,2],[3,4]]:

Goal: 8.
DP: dp = [[1,3],[4,8]], return 8.
Result: 8.

Edge Cases

Single Cell: [[1]] – Return 1.
Single Row: [[1,2,3]] – Return 6.
Single Column: [[1],[2]] – Return 3.

Final Thoughts

The Dynamic Programming solution is a robust pick for LeetCode 64 in Python—intuitive and reliable, with the Space-Optimized version boosting efficiency. For a related challenge, try LeetCode 63: Unique Paths II to add obstacles! Ready to sum paths? Solve LeetCode 64 on LeetCode now and test it with [[1,3,1],[1,5,1],[4,2,1]] or [[1,2,3]] to master minimum sums. Dive in and find the shortest path!