Minimum Path Sum

// C++ implementation
class Solution {
public:
    int calculateMinPath(vector<vector<int>>& matrix) {
        for (int row = matrix.size() - 1; row >= 0; --row) {
            for (int col = matrix[0].size() - 1; col >= 0; --col) {
                if (row == matrix.size() - 1 && col != matrix[0].size() - 1)
                    matrix[row][col] += matrix[row][col + 1];
                else if (col == matrix[0].size() - 1 && row != matrix.size() - 1)
                    matrix[row][col] += matrix[row + 1][col];
                else if (col != matrix[0].size() - 1 && row != matrix.size() - 1)
                    matrix[row][col] += min(matrix[row + 1][col], matrix[row][col + 1]);
            }
        }
        return matrix[0][0];
    }
};

The solution for the problem titled "Minimum Path Sum" involves writing a C++ function that calculates the minimal path sum from the top-left corner to the bottom-right corner of a 2D grid of numbers. Each step either moves to the right or down.

• The class Solution contains the function calculateMinPath which takes a reference to a 2D vector matrix as its argument.
• The solution employs a dynamic programming approach, modifying the matrix in place by starting from the bottom-right corner and iterating towards the top-left corner.
• For each cell (row, col), it adds the minimal value reachable either from the right cell (row, col + 1) or the cell below (row + 1, col), ensuring recursive accumulation of the minimum path sum towards the start.
• Edge cases are handle for cells in the last row and last column, where the path can only proceed in one direction.
• The result, i.e., the minimum path sum from the top-left corner to the bottom-right corner, is stored in matrix[0][0] and returned by the function.

This approach optimizes space usage since it alters the original matrix directly and avoids the need for extra storage aside from a few variables for iteration and comparison. The implementation is efficient, leveraging in-place updates for dynamic programming.

public class Solution {
    public int minimumPathSum(int[][] matrix) {
        for (int row = matrix.length - 1; row >= 0; row--) {
            for (int col = matrix[0].length - 1; col >= 0; col--) {
                if (row == matrix.length - 1 && col != matrix[0].length - 1)
                    matrix[row][col] += matrix[row][col + 1];
                else if (col == matrix[0].length - 1 && row != matrix.length - 1)
                    matrix[row][col] += matrix[row + 1][col];
                else if (col != matrix[0].length - 1 && row != matrix.length - 1)
                    matrix[row][col] += Math.min(matrix[row + 1][col], matrix[row][col + 1]);
            }
        }
        return matrix[0][0];
    }
}

The provided Java solution computes the minimum path sum in a matrix, where you start at the bottom right and can only move up or left. The code modifies the matrix in place by adjusting the original matrix values based on the minimum sum path at each cell, effectively using dynamic programming to avoid redundancy and improve performance. By iterating over the matrix from the bottom-right corner to the top-left corner, the function gradually builds up the path sums:

• Start by iterating from the last row and the last column of the matrix.
• For each cell, update its value by adding the minimum path sum of the adjacent right cell or below cell, ensuring you are never out of bounds.
• If on the last row, but not the last column, add the right cell value to the current cell.
• If on the last column, but not the last row, add the below cell value to the current cell.
• If in any other position that's not on the boundary, add the minimum value of either the right or below cells to the current cell.
• The top-left cell eventually holds the minimum path sum from bottom-right to top-left using the described movements (up or left).

The function returns the value at matrix[0][0], which, after processing, contains the result of the minimum path sum.

// C implementation
int optimalPathSum(int** matrix, int numRows, int* colSize) {
    for (int row = numRows - 1; row >= 0; row--) {
        for (int col = colSize[0] - 1; col >= 0; col--) {
            if (row == numRows - 1 && col != colSize[0] - 1)
                matrix[row][col] += matrix[row][col + 1];
            else if (col == colSize[0] - 1 && row != numRows - 1)
                matrix[row][col] += matrix[row + 1][col];
            else if (col != colSize[0] - 1 && row != numRows - 1)
                matrix[row][col] += (matrix[row + 1][col] < matrix[row][col + 1] ? matrix[row + 1][col]
                                                                                 : matrix[row][col + 1]);
        }
    }
    return matrix[0][0];
}

The provided C code solves the problem of finding the minimum path sum in a matrix, where the path starts from the bottom left and moves only right or up until it reaches the top right of the matrix. The function optimalPathSum executes an in-place modification of the input matrix to compute minimum cost paths.

• The function takes three parameters:

  • matrix - a pointer to a pointer representing the 2D matrix.
  • numRows - the total number of rows in the matrix.
  • colSize - a pointer representing the size of the columns.

• The implementation iterates from the bottom-right corner of the matrix to the top-left. Using nested loops, it updates each cell with the sum of the cell and the minimum cost among the movable adjacent cells (right or up).

• Here's how the function modifies the matrix:

  • If it's in the last row (but not the last column), it only updates the cell value by adding the value of the cell directly to its right.
  • If it's in the last column (but not the last row), it updates the cell value by adding the value of the cell directly above.
  • Otherwise, it updates the cell value by adding the smaller of the values of the cell to the right and the cell above.

• The optimal path sum, which is the minimum sum to reach from the bottom left to the top right, is available at matrix[0][0] after the loops complete. The function returns this value.

This efficient approach ensures a minimal memory footprint as it transforms the input matrix without requiring additional storage for path calculations. By processing from the target towards the beginning, it avoids recalculating paths multiple times which would occur if processed the other way.

// JavaScript function to find minimum path sum in a grid
var calculateMinimumPathSum = function(matrix) {
    for (let row = matrix.length - 1; row >= 0; row--) {
        for (let col = matrix[0].length - 1; col >= 0; col--) {
            if (row === matrix.length - 1 && col !== matrix[0].length - 1)
                matrix[row][col] += matrix[row][col + 1];
            else if (col === matrix[0].length - 1 && row !== matrix.length - 1)
                matrix[row][col] += matrix[row + 1][col];
            else if (col !== matrix[0].length - 1 && row !== matrix.length - 1)
                matrix[row][col] += Math.min(matrix[row + 1][col], matrix[row][col + 1]);
        }
    }
    return matrix[0][0];
};

The JavaScript function calculateMinimumPathSum is designed to calculate the minimum path sum from the top left to the bottom right of a given matrix. This matrix represents a grid where each cell has a certain cost, and the goal is to find the path from the top left corner to the bottom right corner which minimizes the total cost.

Follow these steps in the provided function to solve the problem:

1. Iterate through the matrix starting from the bottom-right corner and move upward and to the left. This reverse iteration helps in solving the problem by breaking it down into smaller subproblems.

2. For each cell, check if it is on the last row, but not on the last column. If true, add the value of the cell directly to the right to the current cell's value.

3. If the cell is in the last column but not the last row, add the value of the cell directly below to the current cell's value.

4. For all other cells (not on the boundary of the grid), add the lesser value between the cell directly to the right and the cell directly below to the current cell's value. This decision ensures that the path taken to any cell is the one which offers the least cumulative cost up to that point.

5. The value in the top-left cell of the matrix after processing represents the minimum path sum from the top-left corner to the bottom-right corner of the original grid.

This approach leverages dynamic programming by using previously computed values to calculate the current cell's value, making it efficient for larger grids.

class Solution:
    def minimumPathSum(self, matrix: List[List[int]]) -> int:
        for row in reversed(range(len(matrix))):
            for col in reversed(range(len(matrix[0]))):
                if row == len(matrix) - 1 and col != len(matrix[0]) - 1:
                    matrix[row][col] += matrix[row][col + 1]
                elif col == len(matrix[0]) - 1 and row != len(matrix) - 1:
                    matrix[row][col] += matrix[row + 1][col]
                elif col != len(matrix[0]) - 1 and row != len(matrix) - 1:
                    matrix[row][col] += min(matrix[row + 1][col], matrix[row][col + 1])
        return matrix[0][0]

The solution provided tackles the problem of determining the minimum path sum from the top-left to the bottom-right corner of a matrix, where only moves to the right and down are allowed. This implementation modifies the input matrix in-place by leveraging dynamic programming to accumulate optimal path sums directly into the matrix, avoiding the need for additional space.

• Start by iterating over the matrix from the bottom to the top and from right to left. This reverse iteration ensures that the solution builds upon already computed sums.
• For each cell, consider three scenarios:
  • If it's the last row (but not the last column), add the value of the immediate right cell to the current cell.
  • If it's the last column (but not the last row), add the value of the cell immediately below.
  • If it's not the edge row or column, add the minimum of the cell to the right and cell below.
• This adjustment to each cell effectively accumulates the minimum path sum leading to that cell.
• Finally, the top-left cell (matrix[0][0]) contains the result—the minimum path sum from top-left to bottom-right of the matrix.

By updating the value of each cell based on its neighbors, the solution efficiently calculates the minimum path without needing extra storage or complex data structures. This approach ensures a space complexity of O(1) and a time complexity of O(M * N) where M and N are the matrix dimensions.