Leetcode: Minimum Path Sum

This question is asked at Amazon, Google, and Bloomberg. Here it is:

Given an 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 the numbers on its path and you can either move down or right at any point in time. This is a dynamic programming problem. Here is the example of a problem:

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

Since we're finding the sum and not the path, we use dynamic programming. If we want to find the path, use the linked list to iterate and see what path is the minimum and append the minimum square to reach for that path. 

So we first check on the first row, and look into the minimum path which is the point to the left. 

This is also the same if we are at the leftmost column of the grid, add the number in the square row above.

Such is the base cases of the dynamic programming table. Else add the minimum of either the sum of the row above or the column to the left, and return the rightmost element of the dynamic programming table. Both time and space complexities are O(M x N). Here's the final code, in Javascript, also a top 2% answer for quickness and top 30% answer for space:

/**

 * @param {number[][]} grid

 * @return {number}

 */

var minPathSum = function(grid) { 

    //start the dynamic programming table 

    var m = grid.length;

    var n = grid[0].length;

    for(var i = 0; i < m; i++) {

        for(var j = 0; j < n; j++) {

            //we first check on the first row, and look into the minimum path which is the point to the left.

            if(i == 0 && j != 0) {

                grid[i][j] = grid[i][j] + grid[i][j - 1];

            }

            //if we are at the leftmost column of the grid, add the number in the square row above.

            else if(i != 0 && j == 0) {

                grid[i][j] = grid[i][j] + grid[i - 1][j];

            }

            //default case

            else if(i == 0 && j == 0) {

               grid[i][j] = grid[i][j]; 

              // add the minimum of either the sum of the row above or the column to the left

            } else {

                grid[i][j] = Math.min(grid[i][j - 1], grid[i - 1][j]) + grid[i][j];

            }

        }  

    }

    //return the rightmost element of the dynamic programming table

    return grid[m - 1][n - 1];

};