Minimum Path Sum In C,CPP,JAVA,PYTHON,C#,JS

/ DSA / By
Spread the love
A close-up shot of a person coding on a laptop, focusing on the hands and screen.

Problem Statement: Minimum Path Sum

You are given a m x n grid filled with non-negative integers. You need to find a path from the top-left corner (0, 0) to the bottom-right corner (m-1, n-1), which minimizes the sum of the numbers along the path. You can only move right or down at any point in time.

Return the minimum path sum.

Example 1:

Input:

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

Output:

7

Explanation: The path to the minimum sum is: 1 → 3 → 1 → 1 → 1, which sums to 7.

Example 2:

Input:

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

Output:

12

Explanation: The path to the minimum sum is: 1 → 2 → 3 → 6 which sums to 12.

Approach:

This problem is a classical Dynamic Programming problem. The goal is to build the solution by incrementally calculating the minimum path sum from the start to the end.

Dynamic Programming Approach:

  1. State Definition:
    • Let dp[i][j] represent the minimum path sum to reach the cell (i, j).
  2. State Transition:
    • The value of dp[i][j] depends on the minimum of two possible directions: either from the left (i, j-1) or from above (i-1, j). Hence: dp[i][j]=grid[i][j]+min⁡(dp[i−1][j],dp[i][j−1])dp[i][j] = grid[i][j] + \min(dp[i-1][j], dp[i][j-1])dp[i][j]=grid[i][j]+min(dp[i−1][j],dp[i][j−1])
    • If you’re in the first row (i == 0), you can only come from the left.
    • If you’re in the first column (j == 0), you can only come from above.
  3. Base Case:
    • The starting point dp[0][0] = grid[0][0].
  4. Final Answer:
    • The answer will be the value at dp[m-1][n-1], which gives the minimum path sum to the bottom-right corner.

Time and Space Complexity:

  • Time Complexity: O(m * n), where m and n are the dimensions of the grid. We need to process each cell exactly once.
  • Space Complexity: O(m * n) for storing the DP table. However, space can be optimized to O(n) by using a 1D array, since each row only depends on the previous row.

Code Implementations in Different Languages:

1. C Language (DP Approach):

#include <stdio.h>

int minPathSum(int** grid, int m, int n) {
    int dp[n];
    
    dp[0] = grid[0][0];
    
    // Fill the first row
    for (int j = 1; j < n; j++) {
        dp[j] = dp[j - 1] + grid[0][j];
    }
    
    // Fill the rest of the grid
    for (int i = 1; i < m; i++) {
        dp[0] += grid[i][0]; // Update the first column
        for (int j = 1; j < n; j++) {
            dp[j] = grid[i][j] + (dp[j - 1] < dp[j] ? dp[j - 1] : dp[j]);
        }
    }
    
    return dp[n - 1];
}

int main() {
    int m = 3, n = 3;
    int grid[3][3] = {
        {1, 3, 1},
        {1, 5, 1},
        {4, 2, 1}
    };
    int* gridPtr[3] = {grid[0], grid[1], grid[2]};
    printf("Minimum Path Sum: %d\n", minPathSum(gridPtr, m, n));  // Output: 7
    return 0;
}

2. C++ Language (DP Approach):

#include <iostream>
#include <vector>
using namespace std;

int minPathSum(vector<vector<int>>& grid) {
    int m = grid.size();
    int n = grid[0].size();
    
    vector<int> dp(n, 0);
    
    dp[0] = grid[0][0];
    
    // Fill the first row
    for (int j = 1; j < n; j++) {
        dp[j] = dp[j - 1] + grid[0][j];
    }
    
    // Fill the rest of the grid
    for (int i = 1; i < m; i++) {
        dp[0] += grid[i][0]; // Update the first column
        for (int j = 1; j < n; j++) {
            dp[j] = grid[i][j] + min(dp[j - 1], dp[j]);
        }
    }
    
    return dp[n - 1];
}

int main() {
    vector<vector<int>> grid = {
        {1, 3, 1},
        {1, 5, 1},
        {4, 2, 1}
    };
    cout << "Minimum Path Sum: " << minPathSum(grid) << endl;  // Output: 7
    return 0;
}

3. Java (DP Approach):

public class MinimumPathSum {
    public static int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        
        int[] dp = new int[n];
        
        dp[0] = grid[0][0];
        
        // Fill the first row
        for (int j = 1; j < n; j++) {
            dp[j] = dp[j - 1] + grid[0][j];
        }
        
        // Fill the rest of the grid
        for (int i = 1; i < m; i++) {
            dp[0] += grid[i][0];  // Update the first column
            for (int j = 1; j < n; j++) {
                dp[j] = grid[i][j] + Math.min(dp[j - 1], dp[j]);
            }
        }
        
        return dp[n - 1];
    }

    public static void main(String[] args) {
        int[][] grid = {
            {1, 3, 1},
            {1, 5, 1},
            {4, 2, 1}
        };
        System.out.println("Minimum Path Sum: " + minPathSum(grid));  // Output: 7
    }
}

4. Python (DP Approach):

def minPathSum(grid):
    m = len(grid)
    n = len(grid[0])
    
    dp = [0] * n
    dp[0] = grid[0][0]
    
    # Fill the first row
    for j in range(1, n):
        dp[j] = dp[j - 1] + grid[0][j]
    
    # Fill the rest of the grid
    for i in range(1, m):
        dp[0] += grid[i][0]  # Update the first column
        for j in range(1, n):
            dp[j] = grid[i][j] + min(dp[j - 1], dp[j])
    
    return dp[-1]

# Test case
grid = [
    [1, 3, 1],
    [1, 5, 1],
    [4, 2, 1]
]
print("Minimum Path Sum:", minPathSum(grid))  # Output: 7

5. C# (DP Approach):

using System;

class Program {
    public static int MinPathSum(int[,] grid) {
        int m = grid.GetLength(0);
        int n = grid.GetLength(1);
        
        int[] dp = new int[n];
        
        dp[0] = grid[0, 0];
        
        // Fill the first row
        for (int j = 1; j < n; j++) {
            dp[j] = dp[j - 1] + grid[0, j];
        }
        
        // Fill the rest of the grid
        for (int i = 1; i < m; i++) {
            dp[0] += grid[i, 0];  // Update the first column
            for (int j = 1; j < n; j++) {
                dp[j] = grid[i, j] + Math.Min(dp[j - 1], dp[j]);
            }
        }
        
        return dp[n - 1];
    }

    static void Main() {
        int[,] grid = {
            {1, 3, 1},
            {1, 5, 1},
            {4, 2, 1}
        };
        Console.WriteLine("Minimum Path Sum: " + MinPathSum(grid));  // Output: 7
    }
}

6. JavaScript (DP Approach):

function minPathSum(grid) {
    let m = grid.length;
    let n = grid[0].length;
    
    let dp = new Array(n).fill(0);
    
    dp[0] = grid[0][0];
    
    // Fill the first row
    for (let j = 1; j < n; j++) {
        dp[j] = dp[j - 1] + grid[0][j];
    }
    
    // Fill the rest of the grid
    for (let i = 1; i < m; i++) {
        dp[0] += grid[i][0]; // Update the first column
        for (let j = 1; j < n; j++) {
            dp[j] = grid[i][j] + Math.min(dp[j - 1], dp[j]);
        }
    }
    
    return dp[n - 1];
}

// Test case
const grid = [
    [1, 3, 1],
    [1, 5, 1],
    [4, 2, 1]
];
console.log("Minimum Path Sum:", minPathSum(grid));  // Output: 7

Complexity Analysis:

Time Complexity:

  • Time Complexity: O(m * n), where m and n are the dimensions of the grid. We need to process each cell exactly once.

Space Complexity:

  • Space Complexity: O(n), where n is the number of columns in the grid. We optimized space by using a 1D array instead of a full 2D DP table.

Conclusion:

The Minimum Path Sum problem can be efficiently solved using dynamic programming. By calculating the minimum path sum progressively from the top-left corner to the bottom-right corner, we can find the optimal path in O(m * n) time with optimized space usage.