grid47 Exploring patterns and algorithms
Oct 31, 2024
6 min read
Solution to LeetCode 64: Minimum Path Sum Problem
Given an m x n grid filled with non-negative integers, find a path from the top-left to the bottom-right corner that minimizes the sum of all numbers along the way. The robot can only move either right or down at each step.
Problem
Approach
Steps
Complexity
Input: An integer 2D grid where grid[i][j] represents the cost at cell (i, j).
Example: Input: grid = [[2,3,4],[5,1,2],[3,2,1]]
Constraints:
• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 200
Output: Return the minimum sum of numbers along the path from the top-left to the bottom-right corner.
Example: Output: 10
Constraints:
• The result will always be less than or equal to 2 * 10^9.
Goal: Calculate the path from the top-left to the bottom-right corner of the grid that minimizes the total sum.
Steps:
• Iterate through each cell of the grid.
• At each cell (i, j), calculate the minimum cost to reach the cell from either the top or the left neighbor.
• For the top row or the leftmost column, only consider cells that exist within the bounds.
• Return the value at the bottom-right corner as the final result.
Goal: The grid size and cell values must adhere to the constraints.
Steps:
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 200
Assumptions:
• The grid is non-empty and contains at least one cell.
• The top-left corner is always the starting point.
• The bottom-right corner is the destination.
• Input: Input: grid = [[2,3,4],[5,1,2],[3,2,1]]
• Explanation: The path 2 → 3 → 1 → 2 → 1 minimizes the sum, giving an output of 10.
• Input: Input: grid = [[1,4,7],[2,5,6]]
• Explanation: The path 1 → 4 → 7 → 6 minimizes the sum, giving an output of 13.
Approach: Use a dynamic programming approach to iteratively calculate the minimum path sum for each cell, based on values from its top or left neighbors.
Observations:
• The problem involves minimizing the sum, so dynamic programming is suitable.
• Each cell's minimum cost depends on the values of its top and left neighbors.
• Start with the base cases for the top row and leftmost column and build up the solution iteratively.
Steps:
• Start from the top-left cell and iterate through each cell in the grid.
• For each cell, calculate the minimum path sum by adding the cell's value to the minimum of its top or left neighbors' values.
• For cells in the top row, only consider the left neighbor (if it exists).
• For cells in the leftmost column, only consider the top neighbor (if it exists).
• Return the value at the bottom-right corner as the result.
Empty Inputs:
• Not applicable as the input grid is guaranteed to have at least one cell.
Large Inputs:
• A grid with maximum size (200 x 200) containing large values close to the upper bound (200).
Special Values:
• A grid where all values are zero, resulting in a minimum path sum of 0.
• A grid where the only path is straight down or straight right.
Constraints:
• Ensure that the solution handles edge cases for single-row or single-column grids efficiently.
intminPathSum(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
// Handle the first row
for (int j =1; j < n; j++) {
grid[0][j] += grid[0][j -1];
}
// Handle the first column
for (int i =1; i < m; i++) {
grid[i][0] += grid[i -1][0];
}
// Fill the rest of the grid
for (int i =1; i < m; i++) {
for (int j =1; j < n; j++) {
grid[i][j] += min(grid[i -1][j], grid[i][j -1]);
}
}
return grid[m -1][n -1];
}
1 : Function Declaration
intminPathSum(vector<vector<int>>& grid) {
This line declares a function named `minPathSum` that takes a 2D vector `grid` representing the grid as input and returns the minimum path sum.
2 : Get Grid Dimensions
int m = grid.size(), n = grid[0].size();
This line gets the dimensions of the grid, `m` for rows and `n` for columns.
This loop iterates over the first row of the grid, starting from the second element. For each cell, it adds the value of the cell to its left to the current cell's value. This represents the minimum path sum to reach that cell from the top-left corner.
4 : Handle First Column
for (int i =1; i < m; i++) {
grid[i][0] += grid[i -1][0];
}
This loop iterates over the first column of the grid, starting from the second row. For each cell, it adds the value of the cell above it to the current cell's value. This represents the minimum path sum to reach that cell from the top-left corner.
5 : Fill the Rest of the Grid
for (int i =1; i < m; i++) {
for (int j =1; j < n; j++) {
grid[i][j] += min(grid[i -1][j], grid[i][j -1]);
}
}
This nested loop iterates over the remaining cells of the grid. For each cell `(i, j)`, it calculates the minimum path sum to reach that cell by adding the minimum of the values from the cell above and the cell to the left to the current cell's value.
6 : Return Minimum Path Sum
return grid[m -1][n -1];
After filling the grid with minimum path sums, the function returns the value at the bottom-right corner, which represents the minimum path sum from the top-left to the bottom-right corner.
Best Case: O(m * n)
Average Case: O(m * n)
Worst Case: O(m * n)
Description: Each cell in the grid is visited exactly once.
Best Case: O(1)
Worst Case: O(1)
Description: The solution modifies the input grid in place, requiring no extra space.
