{x}
blog image

Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

 

Example 1:

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

Example 2:

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] <= 200

Minimum Path Sum

This problem asks to find the minimum path sum from the top-left to the bottom-right of a grid, where movement is restricted to down or right. This is a classic dynamic programming problem.

Approach: Dynamic Programming

We can solve this using dynamic programming by building a table (or matrix) where each cell dp[i][j] represents the minimum path sum to reach the cell at row i and column j.

  1. Initialization:

    • dp[0][0] = grid[0][0] (the starting point).
    • The first row and first column are initialized based on the cumulative sum from the starting point. For example: dp[i][0] = dp[i-1][0] + grid[i][0] and dp[0][j] = dp[0][j-1] + grid[0][j]

  2. Iteration:

    • For each cell dp[i][j] (excluding the first row and column), the minimum path sum is the minimum of the path coming from the top (dp[i-1][j]) and the path coming from the left (dp[i][j-1]), plus the value of the current cell grid[i][j]. This can be represented as: dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

  3. Result:

    • The minimum path sum to reach the bottom-right cell is stored in dp[m-1][n-1], where m and n are the number of rows and columns in the grid, respectively.

Time and Space Complexity

  • Time Complexity: O(m*n), where 'm' and 'n' are the dimensions of the grid. We iterate through each cell once.
  • Space Complexity: O(m*n) in the basic DP approach because we use a DP table of size m x n. This can be optimized to O(n) by using only one row of the DP table (see optimized solution below).

Code Examples

Here's how the solution can be implemented in various programming languages:

Python

def minPathSum(grid):
    m, n = len(grid), len(grid[0])
    dp = [[float('inf')] * n for _ in range(m)]
    dp[0][0] = grid[0][0]
 
    for i in range(m):
        for j in range(n):
            if i > 0:
                dp[i][j] = min(dp[i][j], dp[i-1][j] + grid[i][j])
            if j > 0:
                dp[i][j] = min(dp[i][j], dp[i][j-1] + grid[i][j])
 
    return dp[m-1][n-1]

Java

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
 
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i > 0 && j > 0) {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
                } else if (i > 0) {
                    dp[i][j] = dp[i - 1][j] + grid[i][j];
                } else if (j > 0) {
                    dp[i][j] = dp[i][j - 1] + grid[i][j];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
}

C++

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, INT_MAX));
        dp[0][0] = grid[0][0];
 
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i > 0 && j > 0) {
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
                } else if (i > 0) {
                    dp[i][j] = dp[i - 1][j] + grid[i][j];
                } else if (j > 0) {
                    dp[i][j] = dp[i][j - 1] + grid[i][j];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
};

(Other languages like Javascript, Go, etc., would follow a similar pattern.)

Space Optimization (O(n) Space)

The space complexity can be reduced to O(n) by observing that we only need to store the previous row's values to calculate the current row's values. We can optimize the DP table to use only a single 1D array. This optimization is crucial for very large grids to prevent stack overflow errors. I'll show the optimized Python solution. Other languages can be similarly optimized.

def minPathSumOptimized(grid):
    m, n = len(grid), len(grid[0])
    dp = [float('inf')] * n
    dp[0] = grid[0][0]
 
    for i in range(m):
        new_dp = [float('inf')] * n #Temporary array to avoid overwriting dp prematurely.
        for j in range(n):
            if i > 0:
                new_dp[j] = min(new_dp[j], dp[j] + grid[i][j])
            if j > 0:
                new_dp[j] = min(new_dp[j], new_dp[j-1] + grid[i][j])
        dp = new_dp #Update dp with values from new_dp after the inner loop completes.
 
 
    return dp[n-1]

This optimized version achieves the same result while using significantly less memory. Remember to adapt the optimization to the specific syntax and data structures of other programming languages.