Last updated on March 2nd, 2025 at 04:59 pm

Here, we see a Minimum Path Sum LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Array, Dynamic Programming

Level of Question

Medium

Minimum Path Sum LeetCode Solution

1. 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 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

2. Coding Pattern Used in Solution

The coding pattern used in this problem is Dynamic Programming (DP). This problem is a classic example of a 2D DP Grid Traversal. The goal is to find the minimum path sum from the top-left corner to the bottom-right corner of a grid, where you can only move down or right. The solution builds the result incrementally by solving smaller subproblems and storing intermediate results.

3. Code Implementation in Different Languages

3.1 Minimum Path Sum C++

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

3.2 Minimum Path Sum Java

class Solution {
    public int minPathSum(int[][] grid) {
        if(grid.length == 0)  return 0;
        
        int r = grid.length;
        int c = grid[0].length;
        
        for(int i=0;i<r; i++) {
            for(int j=0; j<c; j++) {
                int leftSum = (j>0) ? grid[i][j-1] : Integer.MAX_VALUE;
                int topSum = (i>0) ? grid[i-1][j] : Integer.MAX_VALUE;
                if(i==0 && j==0) continue;
                
                grid[i][j] += Math.min(leftSum, topSum);
            }
        }
        return grid[r-1][c-1];        
    }
}

3.3 Minimum Path Sum JavaScript

var minPathSum = function(grid) {
    const n = grid.length;
    const m = grid[0].length;
    for(let i=1; i<n; i++) {
        grid[i][0] += grid[i-1][0];
    }
    for(let j=1; j<m; j++) {
        grid[0][j] += grid[0][j-1];
    }
    for(let i=1; i<n; i++) {
        for(let j=1; j<m; j++) {
            grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);
        }
    }
    return grid[n-1][m-1];    
};

3.4 Minimum Path Sum Python

class Solution(object):
    def minPathSum(self, grid):
        m = len(grid)
        n = len(grid[0])
        for i in range(1, n):
            grid[0][i] += grid[0][i-1]
        for i in range(1, m):
            grid[i][0] += grid[i-1][0]
        for i in range(1, m):
            for j in range(1, n):
                grid[i][j] += min(grid[i-1][j], grid[i][j-1])
        return grid[-1][-1]

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(m * n)	O(m * n)
Java	O(m * n)	O(1)
JavaScript	O(m * n)	O(1)
Python	O(m * n)	O(1)

• The problem is solved using Dynamic Programming with a bottom-up approach.
• The in-place modification of the grid in Java, JavaScript, and Python reduces the space complexity to O(1), while C++ uses an additional 2D array, resulting in (O(m \times n)) space complexity.
• The time complexity remains O(m * n) across all implementations, as every cell in the grid is processed once.