O(1) space O(n*m) time python solution (7 lines)


  • 0
    C

    A cell can only be reached from its left or top neighbor. The minimum path sum for any given cell can be calculated by taking the minimum between the two path sums to its neighbors, and adding it to the value currently in the cell (dynamic programming). This can be done in place; simply make one pass through the grid and update each cell with the previously-calculated minimum path sum from its two neighbors.

    class Solution(object):
        def minPathSum(self, grid):
            """
            :type grid: List[List[int]]
            :rtype: int
            """
    
            for i in xrange(1, len(grid[0])):
                grid[0][i] += grid[0][i - 1]
    
            for i in xrange(1, len(grid)):
                grid[i][0] += grid[i - 1][0]
                for j in xrange(1, len(grid[i])):
                    grid[i][j] += min(grid[i - 1][j], grid[i][j - 1]) 
    
            return grid[-1][-1]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.