Minimum Path Sum III in JavaScript (Time Complexity: O(m*n))

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.

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 results in the minimum sum of the numbers along the path. The constraints are that you can only move right or down at any point in time. This problem is significant in various applications such as robotics, pathfinding in games, and network routing.

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 by considering the minimum path sum to reach the current cell from either the cell above it or the cell to the left of it.

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 build up the solution by solving subproblems. This approach ensures that each cell is computed only once, resulting in a time complexity of O(m*n).

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 this is the starting point.

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

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

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

Code Implementation

/**
 * @param {number[][]} grid
 * @return {number}
 */
function minPathSum(grid) {
    const m = grid.length;
    const n = grid[0].length;
    
    // Initialize dp array with the same dimensions as grid
    const dp = Array.from({ length: m }, () => Array(n).fill(0));
    
    // Set the starting point
    dp[0][0] = grid[0][0];
    
    // Fill the first row
    for (let j = 1; j < n; j++) {
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }
    
    // Fill the first column
    for (let i = 1; i < m; i++) {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }
    
    // Fill the rest of the dp array
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    
    // The bottom-right corner contains the minimum path sum
    return dp[m - 1][n - 1];
}

// Example usage:
const grid = [
    [1, 3, 1],
    [1, 5, 1],
    [4, 2, 1]
];
console.log(minPathSum(grid)); // Output: 7

Complexity Analysis

The time complexity of this solution is O(m*n) because we iterate through each cell of the grid once. The space complexity is also O(m*n) due to the additional `dp` array 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 such as an empty grid or a grid with only one row/column.

Thinking and Problem-Solving Tips

When approaching such problems, it is helpful to:

Break down the problem into smaller subproblems.
Consider using dynamic programming to store intermediate results and avoid redundant calculations.
Practice solving similar problems to improve problem-solving skills.

Conclusion

In this blog post, we discussed how to solve the Minimum Path Sum 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: