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
  1. Initialize DP Table.
  • Create \(m \times n\) table, set first cell to grid[0][0].
  1. Fill First Row and Column.
  • Accumulate sums along edges.
  1. Fill Table.
  • For each cell, take min of above and left, add grid value.
  1. 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).

  1. Initialize 1D DP.
  • Size \(n\), set first row sums.
  1. Process Rows.
  • Update array, taking min from above or left.
  1. 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!