[Programming Problem] 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

[Problem Link]

Memoize by simply storing the minimum path to a cell via the top or left cell.

Input:
[[1, 3, 1],
[1, 5, 1],
[4, 2, 1]]

Memoized:
[[ 1, 4, 5 ],
[ 2, 7, 6 ],
[ 6, 8, 7 ]]

Solution will be the bottom right cell in the memoized array.

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function(grid) {
    let ret = new Array(grid.length).fill(0).map((x) => new Array(grid[0].length).fill(0));
    for ( let i = 0 ; i < grid.length ; i++ ) {
        for ( let j = 0 ; j < grid[0].length ; j++ ) {
            if (i===0 && j===0) ret[i][j] = grid[i][j];
            else if (i===0) ret[i][j] = grid[i][j] + ret[i][j-1];
            else if (j===0) ret[i][j] = grid[i][j] + ret[i-1][j];
            else ret[i][j] = grid[i][j] + Math.min(ret[i-1][j], ret[i][j-1]);
        }
    }
    return ret[grid.length-1][grid[0].length-1];
};

softwareeveryday

17 thoughts on “[Programming Problem] Minimum Path Sum”

Leave a Reply

Your email address will not be published.

[Programming Problem] Subsets II
Read More
[Programming Problem] Flatten Binary Tree to Linked List
Read More
[Programming Problem] Largest Number
Read More