Minimum Path Sum - Go Solution

LeetCode

— 2 min read

Solving the LeetCode "Minimum Path Sum" Problem in Go

Difficulty: Medium | Tags: Array, Dynamic Programming, Matrix

Introduction

The "Minimum Path Sum" problem requires finding the path from the top-left to the bottom-right corner of a grid that minimizes the sum of the numbers along the path. This problem is a classic example of dynamic programming, where we break down the problem into smaller subproblems and build up the solution.

Problem Analysis

Given an m x n grid filled with non-negative integers, we need to find the path from the top-left cell (0, 0) to the bottom-right cell (m-1, n-1) with the minimum sum. The movement is restricted to only right or down directions. For example, in the grid [[1,3,1],[1,5,1],[4,2,1]], the minimum path sum is 7 (1 → 3 → 1 → 1 → 1).

Solution Approach

We can solve this problem using dynamic programming. The idea is to create a DP table where each cell (i, j) represents the minimum path sum to reach that cell from the top-left corner. The DP table can be filled iteratively:

  • Initialize the first cell (0, 0) with the grid value.
  • For the first row, each cell can only be reached from the left, so the DP value is the sum of the current grid value and the previous DP value.
  • For the first column, each cell can only be reached from above, so the DP value is the sum of the current grid value and the DP value above.
  • For other cells, the DP value is the grid value plus the minimum of the DP value from the left or above.

Go Implementation


func minPathSum(grid [][]int) int {
    m := len(grid)
    if m == 0 {
        return 0
    }
    n := len(grid[0])
    // Initialize DP table
    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 table
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
        }
    }
    return dp[m-1][n-1]
}
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

Complexity Analysis

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns. We traverse each cell of the grid exactly once.

Space Complexity: O(m * n) for the DP table. However, this can be optimized to O(n) by using a 1D DP array or O(1) by modifying the input grid in-place.

Testing and Examples

Test cases to verify the implementation:

  • Input: [[1,3,1],[1,5,1],[4,2,1]] → Output: 7
  • Input: [[1,2,3],[4,5,6]] → Output: 12
  • Input: [[1]] → Output: 1
  • Input: [[1,2],[1,1]] → Output: 3

Best Practices and Tips

Key takeaways for solving similar problems:

  • Always initialize the DP table with the base case (starting cell).
  • Handle edge cases, such as grids with only one row or one column.
  • Consider space optimization by reusing the input grid or using a 1D array.
  • Use helper functions like min() to improve code readability.

Read more