Minimum Path Sum

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
183 upvotes
Asked in companies
Expedia GroupOlaMathworks

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
2 3
5 9 6
11 5 2
1 1
5
Sample Output 1:
21
5
Explanation For Sample Output 1:
In test case 1, Consider a grid of 2*3:


For this the grid the path with minimum value is (0,0) -> (0,1) -> (1,1) -> (1,2). And the sum along this path is 5 + 9 +5 + 2 = 21. So the ans is 21.

In test case 2, The given grid is:


For this the grid the path with minimum value is (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2).The sum along this path is 1 + 2 + 3 + 4 + 9 = 19.
Sample Input 2:
2
2 2
5 6
1 2
3 3
1 2 3
4 5 4
7 5 9
Sample Output 2:
8
19
Explanation For Sample Output 2:
In test case 1, For this the grid the path with minimum value is (0,0) -> (1,0) -> (1,1). The sum along this path is 5 + 1 + 2 = 8.

In test case 2, The given grid is:


For this the grid the path with minimum value is (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2).The sum along this path is 1 + 2 + 3 + 4 + 9 = 19.
Hint

The very first approach can be to try all possible paths from top left to bottom right and minimize the path sum among the valid ones.

Approaches (3)
Brute Force

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')
Time Complexity

O(2 ^ (N + M)), Where ‘N’ is the number of rows and ‘M’ is the number of columns in the grid.

 

Since we are making 2 recursive calls for each cell visited with the maximum length covered will be (N + M). Thus the time complexity will be O(2 ^ (N + M)).

Space Complexity

O(N + M), Where ‘N’ is the number of rows and ‘M’ is the number of columns in the grid.

 

Since extra space is used by the recursion stack which goes to a maximum depth of N + M. Thus the space complexity will be O(N + M).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Minimum Path Sum
Full screen
Console