Minimum Path Sum II in C++ (O(n * m) Time Complexity)

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:

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

Note:

Convert the previous solution to an iterative one. Your algorithm should run in O(n * m) time and use O(n * m) extra space.

Understanding the Problem

The core challenge of this problem is to find the path from the top-left corner to the bottom-right corner of a grid that minimizes the sum of the numbers along the path. The constraints are that you can only move either down or right at any point in time. This problem is a classic example of dynamic programming, where we need to break down the problem into smaller subproblems and solve them optimally.

Approach

To solve this problem, we can use dynamic programming. The idea is to create a 2D array dp where dp[i][j] represents the minimum path sum to reach cell (i, j). We can fill this array iteratively by considering the minimum path sum to reach the current cell from either the cell above it or the cell to its left.

Initial Naive Solution

A naive solution would involve exploring all possible paths from the top-left to the bottom-right corner, which would be highly inefficient due to the exponential number of possible paths.

Optimized Solution

The optimized solution uses dynamic programming to fill the dp array iteratively. This approach ensures that we only compute the minimum path sum for each cell once, resulting in a time complexity of O(n * m) and a space complexity of O(n * m).

Algorithm

1. Initialize a 2D array dp with the same dimensions as the input grid.

2. Set dp[0][0] to grid[0][0] since that's the starting point.

3. Fill the first row and first column of dp since there's only one way to reach any cell in the first row (from the left) and the first column (from above).

4. For each cell (i, j) in the grid, set dp[i][j] to the value of the current cell plus the minimum of the values from the cell above it and the cell to its left.

5. The value at dp[m-1][n-1] will be the minimum path sum from the top-left to the bottom-right corner.

Code Implementation


#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int minPathSum(vector<vector<int>>& grid) {
    int m = grid.size();
    int n = grid[0].size();
    
    // Create a 2D dp array with the same dimensions as grid
    vector<vector<int>> dp(m, vector<int>(n, 0));
    
    // Initialize the starting point
    dp[0][0] = grid[0][0];
    
    // Fill the first row
    for (int j = 1; j < n; ++j) {
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }
    
    // Fill the first column
    for (int i = 1; i < m; ++i) {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }
    
    // Fill the rest of the dp array
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    
    // The bottom-right corner contains the minimum path sum
    return dp[m - 1][n - 1];
}

int main() {
    vector<vector<int>> grid = {
        {1, 3, 1},
        {1, 5, 1},
        {4, 2, 1}
    };
    
    cout << "Minimum Path Sum: " << minPathSum(grid) << endl;
    return 0;
}

Complexity Analysis

The time complexity of this solution is O(n * m) because we iterate through each cell of the grid once. The space complexity is also O(n * m) due to the additional 2D array dp used to store the minimum path sums.

Edge Cases

Some potential edge cases include:

An empty grid: The function should handle this gracefully, possibly by returning 0 or an appropriate error message.
A grid with only one row or one column: The function should still correctly compute the minimum path sum.

Testing

To test the solution comprehensively, consider the following test cases:

A grid with all zeros.
A grid with increasing numbers.
A grid with random non-negative numbers.
Edge cases like an empty grid or a grid with only one row/column.

Thinking and Problem-Solving Tips

When approaching dynamic programming problems, it's crucial to:

Understand the problem constraints and requirements.
Break down the problem into smaller subproblems.
Think about how to build the solution iteratively or recursively.
Consider edge cases and test your solution thoroughly.

Conclusion

In this blog post, we discussed how to solve the "Minimum Path Sum II" problem using dynamic programming. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for developing strong problem-solving skills and preparing for technical interviews.

Additional Resources

For further reading and practice, consider the following resources: