Accepted Python DP solution, O(n) time and no extra space


  • 0
    X
    class Solution:
        # @param grid, a list of lists of integers
        # @return an integer
        def minPathSum(self, grid):
            n = len(grid)
            m = len(grid[0])
            for i in range(1, n):
                grid[i][0] = grid[i-1][0] + grid[i][0]
            for i in range(1, m):
                grid[0][i] = grid[0][i-1] + grid[0][i]
            for i in range(1, m):
                for j in range(1, n):
                    grid[j][i] = min(grid[j][i-1], grid[j-1][i])+grid[j][i]
            return grid[n-1][m-1]

  • 0
    Y

    Is it this O(n^2) time?


  • 0
    X

    I think it's O(N), or say O(mn). Since the algorithm takes (1+m-1+n-1+2*(m-1)*(n-1)) steps, the runtime complexity should be O(mn), or say O(N) where N is the total number of elements in the grid. Why do you think it makes O(n^2)?


  • 0
    Y

    i think we are talking about the same thing. i mistakenly assumed m~n.Thank you.


  • 0
    X

    No problem. :)


Log in to reply
 

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