Minimum Path sum

64.Minimum Path Sum

Array

Dynamic Programming

Matrix

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. You can only move either down or right at any point in time.

Example:

Input:

grid = [[1,3,1],[1,5,1],[4,2,1]]

→

Output:

7

Algorithm:

1. Start from bottom-right corner
2. For each cell, add minimum path from right or below
3. Handle edge cases (bottom row, rightmost column)
4. Final result in top-left cell

Complexity:

Time: O(m*n) | Space: O(1) since modifying input grid

Java Solution:

public int minPathSum(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    
    for (int i = m - 1; i >= 0; i--) {
        for (int j = n - 1; j >= 0; j--) {
            if (i == m - 1 && j == n - 1) continue;  // Skip bottom-right cell
            else if (i == m - 1)  // Bottom row: can only move right
                grid[i][j] += grid[i][j + 1];  
            else if (j == n - 1)  // Rightmost column: can only move down
                grid[i][j] += grid[i + 1][j];
            else  // Choose minimum path from right or below
                grid[i][j] += Math.min(grid[i + 1][j], grid[i][j + 1]);
        }  
    }
     
    return grid[0][0];  // Top-left contains minimum path sum
}

Python Solution:

def minPathSum(self, grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])
    
    for i in range(m-1, -1, -1):
        for j in range(n-1, -1, -1):
            if i == m-1 and j == n-1:  # Skip bottom-right
                continue
            elif i == m-1:  # Bottom row
                grid[i][j] += grid[i][j+1]
            elif j == n-1:  # Rightmost column
                grid[i][j] += grid[i+1][j]
            else:  # Choose minimum path
                grid[i][j] += min(grid[i+1][j], grid[i][j+1])
                
    return grid[0][0]

C++ Solution:

class Solution {
public:
    int minPathSum(vectorint>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        
        for(int i = m-1; i >= 0; i--) {
            for(int j = n-1; j >= 0; j--) {
                if(i == m-1 && j == n-1) continue;
                else if(i == m-1)
                    grid[i][j] += grid[i][j+1];
                else if(j == n-1)
                    grid[i][j] += grid[i+1][j];
                else
                    grid[i][j] += min(grid[i+1][j], grid[i][j+1]);
            }
        }
        
        return grid[0][0];
    }
};