Minimum Path Sum Medium 0 attempts
LeetCode ↗

Minimum Path Sum

Medium Dynamic ProgrammingMemoization LeetCode

You're given an m x n grid filled with non-negative numbers. Starting at the top-left cell and moving only right or down at each step, find a path to the bottom-right cell that keeps the sum of the visited values as low as possible, and return that sum.

Input Format
Implement minPathSum(grid). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

Input
grid = [[1,3,1],[1,5,1],[4,2,1]]
Output
7

Example 2

Input
grid = [[5]]
Output
5
Constraints
  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 100
Test Cases (2)
Case 1
Args: [[[1,3,1],[1,5,1],[4,2,1]]] Expected: 7
Case 2
Args: [[[5]]] Expected: 5
Topics
Dynamic ProgrammingMemoization

DP

javascript
function minPathSum(grid) {
  const m = grid.length, n = grid[0].length;
  for (let i = 0; i < m; i++)
    for (let j = 0; j < n; j++) {
      if (i === 0 && j === 0) continue;
      const top = i > 0 ? grid[i-1][j] : Infinity;
      const left = j > 0 ? grid[i][j-1] : Infinity;
      grid[i][j] += Math.min(top, left);
    }
  return grid[m-1][n-1];
}

Time: O(mn) | Space: O(1)

Saved in this browser only. Private to you.

JavaScript