LeetCode 64. Minimum Path Sum



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.

Note: You can only move either down or right at any point in time.


Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.



Python Solution

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        min_paths = [[0 for j in range(0, len(grid[0]))] for i in range(0, len(grid))]

        min_paths[0][0] = grid[0][0]
        for j in range(1, len(grid[0])):
            min_paths[0][j] = min_paths[0][j - 1] + grid[0][j]

        for i in range(1, len(grid)):
            min_paths[i][0] = min_paths[i - 1][0] + grid[i][0]
        for i in range(1, len(grid)):
            for j in range(1, len(grid[0])):
                min_paths[i][j] = min(min_paths[i][j - 1], min_paths[i - 1][j]) + grid[i][j]
        return min_paths[len(grid) - 1][len(grid[0]) - 1]
  • Time complexity: O(MN). We traverse the entire matrix once.
  • Space complexity: O(MN). Another matrix of the same size is used.

2 Thoughts to “LeetCode 64. Minimum Path Sum”

Leave a Reply

Your email address will not be published. Required fields are marked *