Minimum Path Sum — Grid DP

Sanjeev SharmaSanjeev Sharma
1 min read

Advertisement

Problem

Find minimum sum path from top-left to bottom-right (right/down only).


Solutions

Python

class Solution:
    def minPathSum(self, grid: list[list[int]]) -> int:
        m,n=len(grid),len(grid[0])
        for i in range(m):
            for j in range(n):
                if i==0 and j==0: continue
                elif i==0: grid[i][j]+=grid[i][j-1]
                elif j==0: grid[i][j]+=grid[i-1][j]
                else: grid[i][j]+=min(grid[i-1][j],grid[i][j-1])
        return grid[m-1][n-1]

C++

class Solution {
public:
    int minPathSum(vector<vector<int>>& g){
        int m=g.size(),n=g[0].size();
        for(int i=0;i<m;i++) for(int j=0;j<n;j++){
            if(!i&&!j) continue;
            else if(!i) g[i][j]+=g[i][j-1];
            else if(!j) g[i][j]+=g[i-1][j];
            else g[i][j]+=min(g[i-1][j],g[i][j-1]);
        }
        return g[m-1][n-1];
    }
};

Complexity

  • Time: O(m*n) | Space: O(1) (in-place)

Advertisement

Sanjeev Sharma

Written by

Sanjeev Sharma

Full Stack Engineer · E-mopro