Sponsored
Sponsored
This approach involves modifying the input grid in place to store the minimum path sum to each cell. Since we can only move right or down, the minimum path sum to each cell is the value of that cell plus the minimum of the sum from the above or left cell. Start by updating the first row and column as they can only be reached by a single direction. Then, fill in the rest of the grid by selecting the minimum path from top or left for each cell.
Time Complexity: O(m * n) where m is the number of rows and n is the number of columns, as each cell is visited once.
Space Complexity: O(1) as we modify the grid in place.
1class Solution {
2 public int minPathSum(int[][] grid) {
3 int m = grid.length;
4 int n = grid[0].length;
5 for (int i = 1; i < m; i++) {
6 grid[i][0] += grid[i - 1][0];
7 }
8 for (int j = 1; j < n; j++) {
9 grid[0][j] += grid[0][j - 1];
10 }
11 for (int i = 1; i < m; i++) {
12 for (int j = 1; j < n; j++) {
13 grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
14 }
15 }
16 return grid[m - 1][n - 1];
17 }
18}This Java implementation follows the same logic as C and C++. It updates the grid in place and returns the final minimum path sum, which is stored in the bottom-right cell.
Rather than modifying the input grid, this approach uses an additional 2D array to store the minimum path sums. Start by initializing the first cell to the first cell of the grid. For the first row and first column, accumulate sums as they can only come from one direction. For the rest of the cells, compute the minimum path by taking the minimum of the paths leading from the top or left cell, and store the result in the auxiliary DP array.
Time Complexity: O(m * n).
Space Complexity: O(m * n) due to the additional 2D array used.
1 public int MinPathSum(int[][] grid) {
int m = grid.Length;
int n = grid[0].Length;
int[][] dp = new int[m][];
for (int i = 0; i < m; i++) {
dp[i] = new int[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] = grid[i][j] + Math.Min(dp[i-1][j], dp[i][j-1]);
}
}
return dp[m-1][n-1];
}
}The C# implementation utilizes an auxiliary DP array to compute minimum path sums efficiently and ensure the original grid remains unaltered.