NUHMAN.com

Introduction

LeetCode 64: Minimum Path Sum challenges us to find the path with the minimum sum from the top-left to the bottom-right corner of a grid. The only allowed moves are right and down.

This is a classic dynamic programming problem, where the optimal solution to the problem can be built from solutions to smaller subproblems. It is similar in nature to LeetCode 62/63 (Unique Paths), but instead of counting paths, we now compute the path cost.

Problem Statement

Given a m x n grid filled with non-negative numbers, find a path from the top-left to the bottom-right which minimizes the sum of all numbers along its path. You may only move either down or right at any point in time.

Example 1:

go

Input: grid = [
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: The path 1 → 3 → 1 → 1 → 1 minimizes the sum.

Example 2:

go

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

Constraints

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 100

Approach: Dynamic Programming

This problem is ideally suited for bottom-up dynamic programming. Here's how we break it down:

Steps:

1. Create a 2D dp array where each cell dp[i][j] represents the minimum path sum to reach grid[i][j] from grid[0][0].
2. The base case is dp[0][0] = grid[0][0].
3. For the first row, dp[0][j] = dp[0][j-1] + grid[0][j] (since we can only move right).
4. For the first column, dp[i][0] = dp[i-1][0] + grid[i][0] (since we can only move down).
5. For other cells:
6. dp[i][j]=min⁡(dp[i−1][j],dp[i][j−1])+grid[i][j]dp[i][j] = \min(dp[i-1][j], dp[i][j-1]) + grid[i][j]dp[i][j]=min(dp[i−1][j],dp[i][j−1])+grid[i][j]

Go Implementation

go

func minPathSum(grid [][]int) int {
    m := len(grid)
    n := len(grid[0])

    // Create a 2D DP array
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
    }

    dp[0][0] = grid[0][0]

    // Fill first row
    for j := 1; j < n; j++ {
        dp[0][j] = dp[0][j-1] + grid[0][j]
    }

    // Fill first column
    for i := 1; i < m; i++ {
        dp[i][0] = dp[i-1][0] + grid[i][0]
    }

    // Fill the rest of the grid
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
        }
    }

    return dp[m-1][n-1]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

Optimized Space Version (1D DP Array)

You can optimize the space complexity to O(n):

go

func minPathSum(grid [][]int) int {
    m := len(grid)
    n := len(grid[0])
    dp := make([]int, n)

    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if i == 0 && j == 0 {
                dp[j] = grid[i][j]
            } else if i == 0 {
                dp[j] = dp[j-1] + grid[i][j]
            } else if j == 0 {
                dp[j] = dp[j] + grid[i][j]
            } else {
                dp[j] = min(dp[j], dp[j-1]) + grid[i][j]
            }
        }
    }

    return dp[n-1]
}

Time and Space Complexity

MetricComplexityTime ComplexityO(m * n)Space ComplexityO(n) optimized

• Time is O(m * n) since every cell is visited once.
• Space can be O(m * n) for the 2D version, or O(n) for the optimized 1D version.

Edge Cases

• 1x1 grid: just return the single cell value.
• All values are 0: total sum will be 0.
• Path with only one row or one column.

Conclusion

LeetCode 64 is a classic grid-based DP problem that reinforces how subproblem results can be reused to construct the optimal solution. With a simple recurrence and thoughtful space optimization, it can be solved efficiently even for large grids.