Last Updated: 26 Dec, 2020

Minimum Path Sum

Moderate

Asked in companies

Solve now

Problem statement

Ninjaland is a country in the shape of a 2-Dimensional grid 'GRID', with 'N' rows and 'M' columns. Each point in the grid has some cost associated with it.

Find a path from top left i.e. (0, 0) to the bottom right i.e. ('N' - 1, 'M' - 1) which minimizes the sum of the cost of all the numbers along the path. You need to tell the minimum sum of that path.

Note:

You can only move down or right at any point in time.

Input format :

The first line contains an integer 'T' denoting the number of test cases. 

The first line of each test case contains two space-separated integers 'N' and ‘M’ representing the number of rows and number of columns in the grid, respectively. 

Next 'N' lines will have 'M' space-separated integers, each line denotes cost values of that row.

Output format:

For each test case, print the minimum sum of the path from top left to bottom right.

Note:

You don't need to print anything, it has already been taken care of. Just implement the given function.

Follow Up:

Can you solve this in O(1) space complexity?

Constraints:

1 <= T <= 100   
1 <= N, M <= 10^2
1 <= GRID[i][j] <= 10^5

Where 'GRID[i][j]' denotes the value of the cell in the matrix.

Time limit: 1 sec

Solve now

Approaches

01 Approach

The main idea is to use recursion to reduce the big problem into several smaller subproblems.

We will call a minSumHelper function that returns us the minimum Sum path from the current point to destination ('N' - 1, ‘M’ - 1).
From each point ('i' , ‘j’), we have 2 choices:
- We can move right to ('i' , ‘j’ + 1). Then we will do a recursive call with ('i' , ‘j’ + 1) as our starting point, say the sum from this call comes out to be ‘A’.
- Or we can move down to ('i' + 1 , ‘j’). Then we will do a recursive call with ('i' + 1, ‘j’) as our starting point, say the sum from this call comes out to be ‘B’.
- Then our minimum cost from ('i' , ‘j’) to ('N' - 1,'M' - 1) will be 'GRID[i][j]' + min('A','B').
The algorithm for minSumHelper will be as follows:
- Int minSumHelper('GRID', ‘i’, ‘j’, ‘N’, 'M)
  - If ‘i’ >= ‘N’ or ‘j’ >= ‘M’ : , if the point is out of grid.
  - return INT_MAX
  - If ‘i’ == ‘N’ - 1 and j == ‘M’ - 1:
  - return ‘GRID[i][j]’.
  - Int ‘A’ = minSumHelper('GRID', 'i', 'j' + 1, ‘N’, ‘M’)
  - Int 'B' = minSumHelper('GRID', ‘i’ + 1, ‘j’, ‘N’, ‘M’)
  - return 'GRID[i][j]' + min('A','B')

Solve now

02 Approach

We can see that we were solving the same subproblems multiple times. Thus, this problem was exhibiting overlapping subproblems. This means, in this approach, we need to eliminate the need for solving the same subproblems again and again. Thus, the idea is to use Memoization.

The steps are as follows:

Create a ‘lookUp’ table of size ‘N’ * ‘M’ to store the answers to the subproblems where ‘lookUp[i][j]’ denotes minimum path sum from ('i', 'j') to ('N' - 1, 'M' - 1)
Initialize the ‘lookUp’ array with -1 which denotes that it is not calculated yet.
We will call a minSumHelper function that returns us the minimum path sum.
The algorithm for minSumHelper will be as follows:
- Int minSumHelper('GRID', ‘i’, ‘j’, ‘N', ‘M’)
  - If 'i' >= ‘N’ or ‘j’ >= 'M' : , if the point is out of grid.
  - return INT_MAX
  - If ‘i’ == ‘N’ - 1 and ‘j’ == ‘M’ - 1:
  - return 'GRID[i][j]'.
  - If ‘lookUp[i][j]’ != -1: ,means we have already calculated the answer for this sub-problem,
  - return ‘lookUp[i][j]’.
  - Int ‘A’ = minSumHelper('GRID', ‘i’, ‘j’ + 1, ‘N’, 'M')
  - Int ‘B’ = minSumHelper('GRID', 'i' + 1, 'j', ‘N’, ‘M’)
  - ‘lookUp[i][j]’ = ‘GRID[i][j]’ + min('A', ‘B’).
  - Return 'lookUp[i][j]'.

Solve now

03 Approach

Initially, we were breaking the large problem into small problems but now, let us look at it differently. The idea is to solve the small problem first and then reach the final answer. Thus we will be using a bottom-up approach now.

We are using the value of GRID[i][j] only for calculating the dp values. We will use our GRID vector as our dp table.

The steps are as follows:

For ‘i’- ‘N’ - 1 to 0:
For ‘j’- ‘M’ - 1 to 0:
If 'i' = ‘N’ - 1 and ‘j’ = ‘M’ - 1:
continue
else if 'i' = ‘N’ -1:
‘GRID[i][j]’ = ‘GRID[i][j]' + ‘GRID[i][j+1]’.
else if ‘j’ = ‘M’ - 1:
‘GRID[i][j]’ = ‘GRID[i][j]’ + ‘GRID[i+1][j]’.
else
‘GRID[i][j]’ = ‘GRID[i][j]’ + min ( ‘GRID[i+1][j]’ , ‘GRID[i][j+1]’).
Finally, return 'GRID[0][0]'.

Solve now