LeetCode 64: Minimum Path Sum

Problem Description

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.

Example 1:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

Example 2:

Input: grid = [[1,2,3],[4,5,6]]
Output: 12

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 200

Difficulty: Medium

Tags: array, dynamic programming, matrix

Rating: 98.63%

Solution

Here’s my Python solution to this problem:

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[0] * n for i in range(m)]
        dp[0][0] = grid[0][0]

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

        for i in range(1, m):
            dp[i][0] = grid[i][0] + dp[i-1][0]
        

        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
        

        return dp[m-1][n-1]

Complexity Analysis

The solution has the following complexity characteristics:

Time Complexity: $O(n²)$
Space Complexity: $O(n)$

Note: This is an automated analysis and may not capture all edge cases or specific algorithmic optimizations.