Skip to main content
CodeEasy v0.1

Minimum Path Sum

Medium Subject: 2-D Dynamic Programming
Time Complexity
O(M * N)
Space Complexity
O(1)

Problem Description

Problem Statement

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. 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

Optimal Solution

Python

Approach: In-Place DP

We can modify the grid in place. For the first row and column, we add the previous cumulative sum. For all other cells, grid[i][j] += min(grid[i-1][j], grid[i][j-1]). The bottom-right cell will contain the minimum path sum.

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])

        for i in range(1, m): grid[i][0] += grid[i-1][0]
        for j in range(1, n): grid[0][j] += grid[0][j-1]

        for i in range(1, m):
            for j in range(1, n):
                grid[i][j] += min(grid[i-1][j], grid[i][j-1])

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