64. Minimum Path Sum

Minimum Path Sum

Problem Description

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

Note: You can only move down or right at any 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] <= 100

Approach) Memoization

/**
 * @param {number[][]} grid
 * @return {number}
 */
// add memoization
var minPathSum = function(grid) {

    //i rows, j cols
    const calculate = (i, j, grid) => {
        if(i === grid.length || j === grid[0].length){
            return 9999999999
        }
        
        if(i === grid.length - 1 && j === grid[0].length - 1){
            return grid[i][j]
        }
        
        if(memo[i][j]){
            return memo[i][j]
        }
        
        memo[i][j] = grid[i][j] + Math.min(calculate(i + 1, j, grid), calculate(i, j + 1, grid))
        return memo[i][j]
    }
    
    
    
    const memo = new Array(grid.length)
    for(let i = 0; i < memo.length; i++){
        memo[i] = new Array(grid[0].length)
    }
    return calculate(0, 0, grid)
};

Approach) Dynamic Programming

var minPathSum = function(grid) {
    if(!grid) return 0;
    
    let row = grid.length;
    let column = grid[0].length;
    
    let res = [0];
    for(let i = 0; i < row; i++){
        for(let j = 0; j < column; j++){
            if(i === 0){
                res.push(res[j] + grid[i][j]);
            } else if(j === 0){
                res[j + 1] += grid[i][j];
            } else {
                res[j + 1] = Math.min(res[j], res[j + 1]) + grid[i][j];
            }
        }
    }
    
    return res[column];
};

Approach) Native Solution

/**
 * @param {number[][]} grid
 * @return {number}
 */

 var checkUndefined = (i, j, grid) => {
    if(i > grid.length - 1 || j > grid[0].length - 1){
        return Infinity;
    }
    return grid[i][j];
}
var minPathSum = function(grid) {
    var i = grid.length - 1;
    var j = grid[0].length - 1;
    
    
    while(true){
          if(j < 0){
            i--;
            j = grid[0].length - 1;
        }
     if(i < 0){
            break;
        }
      
        grid[i][j] = grid[i][j] + (Math.min(checkUndefined(i+1,j, grid), checkUndefined(i, j+1, grid)) === Infinity ? 0 :         Math.min(checkUndefined(i+1,j, grid), checkUndefined(i, j+1, grid)));
        j--;
     
    }
    return grid[0][0]
    
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem 64. Minimum Path Sum

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!