Minimum Path Sum Medium 0 attempts
LeetCode ↗

Minimum Path Sum

Medium Dynamic ProgrammingMemoization LeetCode

Given an m×n grid of non-negative numbers, find a path from top-left to bottom-right minimizing the sum.

Example: grid = [[1,3,1],[1,5,1],[4,2,1]] → Output: 7 (1→3→1→1→1)

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

DP

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