Minimum Path Sum

Posted: 26 Dec, 2020
Difficulty: Moderate


Try Problem

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.

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.
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?
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
Approach 1

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


  1. We will call a minSumHelper function that returns us the minimum Sum path from the current point to destination ('N' - 1, ‘M’ - 1).
  2. 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').
  3. 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')
Try Problem