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.
Note: You can only move either down or right at any point in time.
Link: https://leetcode.com/problems/minimum-path-sum/
Problem Explanation with examples:-
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 → 3 → 6 minimizes the sum.
Constraints
m == grid.lengthn == grid[i].length1 <= m, n <= 2000 <= grid[i][j] <= 100
Intuition:-
The minimum path from the top left to the bottom right will be the same as the minimum path from the bottom right to the top left. So we can start from the bottom right corner and move to the top left corner trying all the possible paths.
All possible paths means recursion. But recursion will be very slow. DP can be used to speed up the process. Tabulation is also feasible. We will go with Tabulation.
We will use a 2D array to store the minimum path sum from the bottom right to the top left. The last element of the array will be the minimum path sum from the top left to the bottom right.
Iterate through the array from the bottom right to the top left. For each element, we will add the minimum of the element below and the element to the right. This will be the minimum path sum from that element to the bottom right corner.
The last element of the array will be the minimum path sum from the top left to the bottom right.
Solution:-
Create a 2D array of size m*n. m and n are the number of rows and columns in the grid.
Iterate through the grid from the first row to the last row and from the first column to the last column.
If the current element is the first element, then dp[i][j] = grid[i][j]. This is because the first element is the starting point and it does not have any previous element.
If the current element is in the first row, then dp[i][j] = grid[i][j] + dp[i][j-1]. This is because the element to the left is the only element that can be reached from the current element.
If the current element is in the first column, then dp[i][j] = grid[i][j] + dp[i-1][j]. This is because the element below is the only element that can be reached from the current element.
If the current element is neither in the first row nor in the first column, then dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). This is because the element below and the element to the left are the only elements that can be reached from the current element.
Return dp[m-1][n-1]. This is because the last element of the array will be the minimum path sum from the top left to the bottom right.
Code:-
JAVA Solution
class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 && j == 0) {
dp[i][j] = grid[i][j];
} else if (i == 0) {
dp[i][j] = grid[i][j] + dp[i][j - 1];
} else if (j == 0) {
dp[i][j] = grid[i][j] + dp[i - 1][j];
} else {
dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m - 1][n - 1];
}
}
Python Solution
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
dp = [[0 for i in range(n)] for j in range(m)]
for i in range(m):
for j in range(n):
if i == 0 and j == 0:
dp[i][j] = grid[i][j]
elif i == 0:
dp[i][j] = grid[i][j] + dp[i][j-1]
elif j == 0:
dp[i][j] = grid[i][j] + dp[i-1][j]
else:
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
return dp[m-1][n-1]
Complexity Analysis:-
TIME:-
Time complexity is O(m*n) where m and n are the number of rows and columns in the grid. We iterate through the grid once.
SPACE:-
Space complexity is O(m*n) where m and n are the number of rows and columns in the grid. We create a 2D array of size m*n.