Code Implementation

class Solution:
    def minPathSum(self, grid):
        if not grid or not grid[0]:
            return 0
        m, n = len(grid), len(grid[0])
        dp = [[0 for _ in range(n)] for _ in range(m)]
        dp[0][0] = grid[0][0]
        # Fill first column
        for i in range(1, m):
            dp[i][0] = dp[i-1][0] + grid[i][0]
        # Fill first row
        for j in range(1, n):
            dp[0][j] = dp[0][j-1] + grid[0][j]
        # Fill the rest
        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]
      

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

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < m; i++)
            dp[i][0] = dp[i-1][0] + grid[i][0];
        for (int j = 1; j < n; j++)
            dp[0][j] = dp[0][j-1] + grid[0][j];
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }
}
      

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

Problem Description

You are given a 2D grid of non-negative integers called grid. Your task is to find a path from the top-left corner (cell [0][0]) to the bottom-right corner (cell [m-1][n-1]). You can only move either down or right at any point in time. The path should minimize the sum of all numbers along its way. Return the minimum path sum.

• Each move can only go to the cell directly below or to the right.
• There is always at least one valid path.
• You cannot move diagonally or revisit a cell.

Thought Process

At first glance, you might think about trying all possible paths from the top-left to the bottom-right and picking the one with the smallest sum. However, since you can only move right or down, the number of possible paths grows quickly with the grid size, making brute-force infeasible for large grids.

To optimize, notice that the minimum path to any cell depends only on the minimum paths to the cell above it and to the left of it. This suggests a dynamic programming approach, where you build up the solution by combining solutions to smaller subproblems.

The key insight is that for each cell, you only need to know the minimum sum to reach the cell above and the cell to the left, and then add the current cell's value. This way, you avoid recalculating the same paths multiple times.

Solution Approach

• Step 1: Create a 2D array dp of the same size as grid. Each cell dp[i][j] will store the minimum path sum to reach grid[i][j] from the start.
• Step 2: Initialize dp[0][0] to grid[0][0] since that's where you start.
• Step 3: Fill in the first row and first column:
  • For the first row, you can only come from the left, so each dp[0][j] is dp[0][j-1] + grid[0][j].
  • For the first column, you can only come from above, so each dp[i][0] is dp[i-1][0] + grid[i][0].
• Step 4: For the rest of the cells, set dp[i][j] to the minimum of dp[i-1][j] (from above) and dp[i][j-1] (from left), plus grid[i][j].
• Step 5: The answer is in dp[m-1][n-1], the bottom-right cell.

This approach uses a 2D array for clarity, but you can optimize space by using a single array, since each cell only depends on the current and previous rows.

Example Walkthrough

Consider the following grid:

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

1. Start at [0][0] (value 1).
2. First row:
   • dp[0][1] = dp[0][0] + grid[0][1] = 1 + 3 = 4
   • dp[0][2] = dp[0][1] + grid[0][2] = 4 + 1 = 5
3. First column:
   • dp[1][0] = dp[0][0] + grid[1][0] = 1 + 1 = 2
   • dp[2][0] = dp[1][0] + grid[2][0] = 2 + 4 = 6
4. Fill in the rest:
   • dp[1][1] = min(dp[0][1], dp[1][0]) + grid[1][1] = min(4,2) + 5 = 2 + 5 = 7
   • dp[1][2] = min(dp[0][2], dp[1][1]) + grid[1][2] = min(5,7) + 1 = 5 + 1 = 6
   • dp[2][1] = min(dp[1][1], dp[2][0]) + grid[2][1] = min(7,6) + 2 = 6 + 2 = 8
   • dp[2][2] = min(dp[1][2], dp[2][1]) + grid[2][2] = min(6,8) + 1 = 6 + 1 = 7
5. The minimum path sum is dp[2][2] = 7.

The path is 1 → 3 → 1 → 1 → 1, totaling 7.

Time and Space Complexity

• Brute-force approach:
  • Would try every possible path, leading to exponential time: O(2^(m+n)) for an m x n grid.
  • Space complexity: O(m+n) for recursion stack (if using DFS).
• Dynamic programming approach:
  • Time complexity: O(m*n), since each cell is visited once and does constant work.
  • Space complexity: O(m*n) for the DP table. Can be optimized to O(n) if using a single row.

Summary

The Minimum Path Sum problem is a classic example of using dynamic programming to avoid redundant computation. By breaking the problem into smaller subproblems and building up the solution, we efficiently find the minimum sum path in a 2D grid. The key insight is that each cell only depends on its top and left neighbors, allowing us to use a simple DP table to achieve optimal performance.