Minimum Path Sum - Leetcode Solution

Problem statement:

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:

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

Solution:

To solve this problem, we can use dynamic programming. We can create a 2D matrix of the same size as the input matrix and fill it with the minimum sum required to reach each cell.

Let us assume that, the top-left corner of the input matrix is (0, 0) and the bottom-right corner is (m - 1, n - 1). For the first row and first column, we can directly copy the value from the input matrix because there is only one way to reach each cell in these rows and columns i.e., moving right in the first row and moving down in the first column.

For the rest of the matrix, we can determine the minimum sum required to reach each cell by taking the minimum value from the previous cells in the same row and column and adding the current cell value. We can express this idea using the following recurrence relation:

dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

where dp[i][j] represents the minimum sum required to reach cell (i, j) in the input matrix, and grid[i][j] represents the cell value in the input matrix.

After filling the dp matrix, the minimum sum required to reach the bottom-right corner will be present in dp[m-1][n-1]. So, we return that value as the answer.

Here is the Python code to implement the above approach:

def minPathSum(grid): m, n = len(grid), len(grid[0]) dp = [[0 for _ in range(n)] for _ in range(m)]

# initialize the first row
dp[0][0] = grid[0][0]
for j in range(1, n):
    dp[0][j] = dp[0][j-1] + grid[0][j]

# initialize the first column
for i in range(1, m):
    dp[i][0] = dp[i-1][0] + grid[i][0]

# fill the rest of the matrix
for i in range(1, m):
    for j in range(1, n):
        dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

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

Time complexity: O(m*n), where m and n are the dimensions of the input matrix.

Space complexity: O(mn), since we are using a 2D matrix of size mn to store the intermediate results.

1