Minimum Path Sum medium

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 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 Explanation: Because the path 1→ 2 → 3 → 6 minimizes the sum.

Steps

1. Initialization: Create a DP (dynamic programming) table of the same size as the grid. Initialize the top-left cell of the DP table with the value of the top-left cell of the grid.

2. First Row and First Column: Fill the first row and first column of the DP table. The value at each cell DP[i][j] will be the sum of the values along the path from the top-left cell to that cell. This means accumulating the values from the left or from above.

3. Iterative DP: Iterate through the remaining cells of the DP table. For each cell DP[i][j], the minimum path sum to reach that cell is the minimum of the path sum from the cell above (DP[i-1][j]) and the path sum from the cell to the left (DP[i][j-1]), plus the value of the current cell in the grid (grid[i][j]).

4. Result: The bottom-right cell of the DP table DP[m-1][n-1] will contain the minimum path sum from the top-left to the bottom-right cell.

Explanation

This problem is a classic dynamic programming problem. We use dynamic programming because we can break down the problem into smaller overlapping subproblems. The minimum path sum to reach a cell is dependent on the minimum path sums to reach the cells above and to its left. By storing these intermediate results in the DP table, we avoid redundant calculations. The iterative approach ensures we calculate the minimum path sum in a bottom-up manner, building up from the known solution at the top-left to the final solution at the bottom-right.

Code

function minPathSum(grid: number[][]): number {
    const m = grid.length;
    const n = grid[0].length;

    // Create DP table and initialize
    const dp: number[][] = Array(m).fill(null).map(() => Array(n).fill(0));
    dp[0][0] = grid[0][0];

    // Fill first row and column
    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];
    }

    // Iterative DP
    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];
        }
    }

    // Result
    return dp[m - 1][n - 1];
}

Complexity

• Time Complexity: O(m*n), where 'm' and 'n' are the dimensions of the grid. We iterate through the DP table once.
• Space Complexity: O(m*n), as we use a DP table of the same size as the grid. We could optimize this to O(min(m,n)) by using a 1D DP array if needed, but it makes the code less readable.