Minimum Path Sum Solution - Leetcode
Leetcode Solution: Understand Leetcode Minimum Path Sum With Brute Force and Optimal Solution
This document presents the solution to the problem 64. Minimum Path Sum - Leetcode. This question is one of the most typical dynamic programming questions that you’ll be asked to solve. Here the solution lies in the very definition of Dynamic Programming, ie., breaking the problem into sub problems and solving them.
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.
Example:
Input:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.
Let’s use the very same example that is there in the question itself:
input := [][]int{
{1, 3, 1},
{1, 5, 1},
{4, 2, 1},
}
In order to solve this question we’ve to travel through all the paths starting from index [0][0] to [2][2]. There are
two kinds of steps that we can take, ie., we can either go left from the current index, →, or we can go to the
element in the next row but in the same column, ↓.
If we take only these two steps then we can reach to element [2][2] from [0][0] via these paths:
- 1→3→5→1→1, sum = 11
- 1→3→1→1→1, sum = 7
- 1→3→5→2→1, sum = 12
- 1→1→4→2→1, sum = 9
- 1→1→5→1→1, sum = 9
- 1→1→5→2→1, sum = 10
We can obtain all these paths using from a brute force approach. Once we reach to the last element then:
- we can then sum up the elements present in the path
- compare that sum with the minimum sum
- if the current sum is lower than the minimum sum then we can replace the value of the minimum sum with the current one
- Once we’ve traversed all the paths then minimum sum will be the answer.
This will be the brute force solution for this problem.
Now, let’s look into a slightly different approach:
- We can reach
[i][j]element only from the elements present at the indexes[i][j - 1]and[i - 1][j]. - If we know the minimum path sum for the elements
[i][j - 1]and[i - 1][j]then the minimum path sum for the element at[i][j]will be minimum betweensum[i][j - 1] + element[i][j]andsum[i - 1][j] + element[i][j]. - So if we need to know the minimum path sum for the elements at
[i][j - 1]and[i - 1][j]
Let’s work on a very simple example to understand this approach. This is the input:
| 1 | 3 |
|---|---|
| 2 | 7 |
and, this is our minimum path sum table:
| 1 | ∞ |
|---|---|
| ∞ | ∞ |
We’ll start from 1 and from here we can go to 3, [0][1] and 2, [1][0] with the sum = 1 + 3 and 1 + 2.
| 1 | 4 |
|---|---|
| 3 | ∞ |
Now, we’re at 4 or [0][1] and from here we can only go to [1][1] so the minimum sum for reaching to that index is 4 + 7 = 11.
| 1 | 4 |
|---|---|
| 3 | 11 |
Next, we pick up 3 or [1][0]. From here we can only go to the index [1][1] with the sum of 3 + 7 = 10. But we’ve
already reached the element at [1][1] using the path 1→4→7 with the sum of 11. Since the new sum is lower than the
previous sum, so we will update it with 10 and this will be minimum path sum for the input.
| 1 | 4 |
|---|---|
| 3 | 10 |
Let’s work on a new input:
input := [][]int{
{1, 3, 1},
{1, 5, 1},
{4, 2, 1},
}
I’ve created an animation for the array traversal of this input:
Now, let’s proceed to the program or code for the solution(which can be found here @ Github as wel).
Note: Make sure to go through the code comments as well. It’ll help you understand the concept better.
func minPathSum(grid [][]int) int {
// sumGrid is a 2D with the same dimension as the grid object
// It will save the minimum path sum for each of the elements
sumGrid := make([][]int, len(grid))
for i := range sumGrid {
sumGrid[i] = make([]int, len(grid[0]))
for j := 0; j < len(grid[i]); j++ {
// in the beginning all the elements are not
// reachable from any other element
// so setting Infinity or math.MaxInt32
sumGrid[i][j] = 1<<31 - 1
}
}
// as the minimum path sum for reaching the first element
// will be the value of first element itself
sumGrid[0][0] = grid[0][0]
for i := 0; i < len(sumGrid); i++ {
for j := 0; j < len(sumGrid[0]); j++ {
if j+1 < len(sumGrid[0]) && sumGrid[i][j+1] > sumGrid[i][j]+grid[i][j+1] {
sumGrid[i][j+1] = sumGrid[i][j] + grid[i][j+1]
}
if i+1 < len(sumGrid) && sumGrid[i+1][j] > sumGrid[i][j]+grid[i+1][j] {
sumGrid[i+1][j] = sumGrid[i][j] + grid[i+1][j]
}
}
}
// returning the last row's last column's value
// as this will contain the minimum path sum for
// the last element
return sumGrid[len(sumGrid)-1][len(sumGrid[0])-1]
}
