LeetCode Solution 64 - Minimum Path Sum

 Problem Statement

The problem "Minimum Path Sum" is stated as follows:

Given an m x n grid filled with non-negative numbers, find a path from the top-left to the 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:

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

Output:

7

Explanation:

The path 1 → 3 → 1 → 1 → 1 gives the minimum sum of 7.

---

Optimal Approach - Dynamic Programming (DP)

Since we are only allowed to move right or down, we can use Dynamic Programming to solve this problem efficiently.

Intuition:

• Let dp[i][j] represent the minimum path sum to reach cell (i, j).

• The only way to reach (i, j) is either from above (i-1, j) or from the left (i, j-1).

• The minimum path sum at dp[i][j] is:

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

• The first row can only be reached from the left, and the first column can only be reached from above, so they must be initialized separately.

---

C++ Solution (Dynamic Programming)

This is the optimal solution that can be directly submitted on LeetCode.

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        
        // Modify grid in-place to save space
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) continue; // Start position
                else if (i == 0) grid[i][j] += grid[i][j-1];
                else if (j == 0) grid[i][j] += grid[i-1][j];
                else grid[i][j] += min(grid[i-1][j], grid[i][j-1]);
            }
        }
        
        return grid[m-1][n-1];
    }
};

Time Complexity:

• O(m * n) → Since we iterate over each cell exactly once.

Space Complexity:

• O(1) → We modify the grid in place, so no extra space is used.

---

Step-by-Step Explanation of Code

Understanding the Algorithm with a Dry Run

Example Grid:

1  3  1
1  5  1
4  2  1

Step-by-Step Execution:

1. Start at (0,0), grid[0][0] = 1 (no change)
2. Fill the first row:
   • grid[0][1] = 1 + 3 = 4
   • grid[0][2] = 4 + 1 = 5
3. Fill the first column:
   • grid[1][0] = 1 + 1 = 2
   • grid[2][0] = 2 + 4 = 6
4. Compute the rest:
   • grid[1][1] = 5 + min(4,2) = 7
   • grid[1][2] = 1 + min(7,5) = 6
   • grid[2][1] = 2 + min(7,6) = 8
   • grid[2][2] = 1 + min(8,6) = 7

Final Grid:

1  4  5
2  7  6
6  8  7

Return grid[2][2] = 7 ✅

---

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Why Not Optimal?
Brute Force (Recursion)	O(2^(m+n))	O(m+n)	Exponential time complexity, slow for large grids.
Memoization (Recursion + DP)	O(m * n)	O(m * n)	Uses extra space for recursion stack & memoization.
2D DP Table	O(m * n)	O(m * n)	Extra space needed for DP table.
In-Place DP (Best Solution)	O(m * n)	O(1)	Modifies input grid, no extra space required. ✅

---

Best Solution & Why It’s Best

The in-place DP approach is the most efficient because: ✅ Time Complexity: O(m * n), iterating each cell once.
✅ Space Complexity: O(1), modifies input grid instead of using extra storage.
✅ No Recursion Overhead: Unlike recursion-based methods.

---

Conclusion & Similar Problems

The Minimum Path Sum problem is a classic Dynamic Programming problem that teaches:

• Grid-based bottom-up DP.
• Optimizing space complexity by modifying the grid in place.
• Pattern recognition for similar problems.

Similar Problems for Practice:

1. Unique Paths
2. Unique Paths II
3. Triangle Minimum Path Sum
4. Dungeon Game

---

Hope this helps! Let me know if you have any questions or want more explanations! 🚀