class Solution: # @param grid, a list of lists of integers # @return an integer def minPathSum(self, grid): n = len(grid) m = len(grid) for i in range(1, n): grid[i] = grid[i-1] + grid[i] for i in range(1, m): grid[i] = grid[i-1] + grid[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]
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)?
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.