Minimum Path Sum II in Python (Iterative, O(n * m) Time and Space 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 minimum path sum from the top-left corner to the bottom-right corner of a grid, where you can only move right or down. This problem is significant in various applications such as robotics, game development, and pathfinding algorithms.

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 based on the following rules:

Start from the top-left corner.
For each cell, the minimum path sum is the value of the cell plus the minimum of the path sums from the cell above or the cell to the left.

We will initialize the first cell with the value of the grid's first cell and then fill the first row and first column separately since they have only one possible path (either from the left or from above).

Algorithm

Here is a step-by-step breakdown of the algorithm:

Create a 2D array `dp` with the same dimensions as the input grid.
Initialize `dp[0][0]` with `grid[0][0]`.
Fill the first row and first column of `dp` by accumulating the values from the grid.
For each cell `(i, j)`, compute `dp[i][j]` as `grid[i][j]` plus the minimum of `dp[i-1][j]` and `dp[i][j-1]`.
The value at `dp[m-1][n-1]` will be the minimum path sum.

Code Implementation

def minPathSum(grid):
    # Get the dimensions of the grid
    m, n = len(grid), len(grid[0])
    
    # Create a 2D dp array with the same dimensions as grid
    dp = [[0] * n for _ in range(m)]
    
    # Initialize the top-left cell
    dp[0][0] = grid[0][0]
    
    # Fill the first row
    for j in range(1, n):
        dp[0][j] = dp[0][j-1] + grid[0][j]
    
    # Fill the first column
    for i in range(1, m):
        dp[i][0] = dp[i-1][0] + grid[i][0]
    
    # Fill the rest of the dp array
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
    
    # The bottom-right cell contains the minimum path sum
    return dp[m-1][n-1]

# Example usage
grid = [
    [1, 3, 1],
    [1, 5, 1],
    [4, 2, 1]
]
print(minPathSum(grid))  # Output: 7

Complexity Analysis

The time complexity of this algorithm 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.
A grid with only one row or one column: The function should still compute the correct path sum.

For example:

grid = [[1]]
print(minPathSum(grid))  # Output: 1

grid = [[1, 2, 3]]
print(minPathSum(grid))  # Output: 6

grid = [[1], [2], [3]]
print(minPathSum(grid))  # Output: 6

Testing

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

Simple grids with small dimensions.
Grids with larger dimensions to test performance.
Grids with varying values to ensure the path sum is computed correctly.

Using a testing framework like `unittest` in Python can help automate and organize these tests.

Thinking and Problem-Solving Tips

When approaching such problems, it is helpful to:

Break down the problem into smaller subproblems.
Think about how to use dynamic programming to store intermediate results.
Consider edge cases and how to handle them.
Practice similar problems to improve problem-solving skills.

Conclusion

In this blog post, we discussed how to solve the Minimum Path Sum problem using an iterative dynamic programming approach. 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 in programming.

Additional Resources

For further reading and practice, consider the following resources: