For today’s post, we’ll discuss the Minimum Path Sum problem from Leetcode.
Table of Contents
What is the Minimum Path Sum problem?
The minimum path sum problem requires us to write a function called minPathSum() that accepts a 2D list called grid. This list represents a 2D grid filled with non-negative numbers.
Our job is to find a path from the top-left to bottom-right corner of the grid, such that the sum of all numbers along the path is the smallest. The function needs to return this minimum sum.
For instance, if we have the following grid, the path that results in the minimum sum is highlighted in yellow.
Our function needs to return the number 14 (which is the sum for the path 1 -> 3 -> 2 -> 3 -> 5).
How to Solve It?
The main idea for solving the minimum path sum problem is to calculate the minimum path sum for EACH cell in the grid. Once we do that, we simply return the minimum sum for the last cell in the grid and the problem is solved.
To implement this solution in Python 3, we need to use three for loops. The solution for this approach is given below. Read on for an easy to understand explanation of how this solution works.
Python Solution For The Minimum Path Sum Problem
def minPathSum(grid):
rows = len(grid)
cols = len(grid[0])
# first row
for i in range(1, cols):
grid[0][i] += grid[0][i-1]
# first col
for i in range(1, rows):
grid[i][0] += grid[i-1][0]
# inner cells
for i in range(1, rows):
for j in range(1, cols):
grid[i][j] += min(grid[i-1][j], grid[i][j-1])
return grid[-1][-1]Step 1: Getting the dimensions of the grid
In the solution above, we first declare two variables rows and cols for storing the number of rows and columns in the grid respectively.
Step 2: Update the cells in the first row
Next, we use a for loop on lines 6 and 7 to iterate over the first row in the grid.
For each cell in the first row, there is only one path to reach that cell. Hence, the minimum sum for each cell in the first row is the sum of all numbers in that row up to the current cell.
For instance, if we have the following grid,
the minimum sum for each cell in the first row is given below:
4 represents the minimum sum for grid[0][1] (which involves the path 1 -> 3) while 6 represents the minimum sum for grid[0][2] (which involves the path 1 -> 3 -> 2).
The first for loop in our solution (lines 6 and 7) updates the cells in the first row to reflect the minimum sum for each cell in that row. This is done using the formula below:
grid[0][i] += grid[0][i-1]
For instance, it updates
grid[0][1]
to
grid[0][1] + grid[0][0] = 3 + 1 = 4.
Next, it updates
grid[0][2]
to
grid[0][2] + grid[0][1] = 2 + 4 = 6.
Step 3: Update the cells in the first column
After updating the cells in the first row, we move on to the first column.
For cells in the first column, there is also only one path to reach that cell. Hence, the minimum sum for each cell is the sum of all numbers in that column up to the current cell.
With reference to Grid A above, the minimum sum for each cell in the first column is given by the numbers in the grid below:
The second for loop in our solution (lines 10 and 11) uses the formula below to update the first column.
grid[i][0] += grid[i-1][0]
For instance, it updates
grid[1][0]
to
grid[1][0] + grid[0][0] = 4 + 1 = 5.
Next, it updates
grid[2][0]
to
grid[2][0] + grid[1][0] = 6 + 5 = 11.
5 represents the minimum sum for grid[1][0] (1 -> 4) while 11 represents the minimum sum for grid[2][0] (1 -> 4 -> 6).
Step 4: Update the remaining cells
After updating the first row and column, we need to update the remaining cells.
For these cells, it is possible to reach the cell from above, or from the left.
As such, we should choose the path that results in a smaller sum.
Say we are considering the yellow cell in the updated grid above, we can reach it from the blue cell or the green cell. Based on the values in the updated grid, we see that the minimum sum for the blue cell is 4 while that for the green cell is 5. Hence, taking the path that passes through the blue cell is preferred.
Therefore, the minimum sum for the yellow cell is 7 + 4 = 11 (this involves the path 1 -> 3 -> 7).
Based on this logic, we can calculate the minimum sum for all the inner cells. The answer is given in the grid below.
Step 5: Return the value in the bottom-right cell
Once we finish doing that, the result required is the value in the bottom-right cell (i.e. 14 in the example above). We simply return the value of that cell and the problem is solved.