Min Cost Path

Moderate
0/80
Average time to solve is 25m
3 upvotes
Asked in companies
SprinklrOYO

Problem statement

You have been given a matrix of ‘N’ rows and ‘M’ columns filled up with integers. Find the minimum sum that can be obtained from a path which starts from the top left corner and ends with the bottom right corner.

From any cell in a row, we can move to the right, down or the down-right diagonal cell. So from a particular cell (row, col), we can move to the following three cells:

Down: (row+1,col)
Right: (row, col+1)
Down right diagonal: (row+1, col+1)
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will contain two integers ‘N’ and ‘M’ denoting the number of rows and columns, respectively.

Next ‘N’ lines contain ‘M’ space-separated integers each denoting the elements in the matrix.
Output Format: 
For each test case, print an integer which represents the minimum sum that can be obtained by travelling a path as described above.

Output for every test case will be printed in a separate line.
Note: 
You don’t need to print anything; It has already been taken care of.
Constraints: 
1 <= T <= 50
1 <= N, M <= 100
-10000 <= cost[i][j] <= 10000

Where ‘T’ is the number of test cases.
Where 'N' is the number of rows in the given matrix, and 'M' is the number of columns in the given matrix.
And, cost[i][j] denotes the value at (i,j) cell in the matrix.

Time limit: 1 sec
Sample Input 1:
2
3 3
2 3 1
1 2 1
2 2 3
2 3
2 3 3
5 2 1
Sample Output 1:
7
5
Explanation of sample input 1:

Example

In the first test case, the minimum cost path will be (0, 0) -> (1, 1) -> (2, 2), So the path sum will be (2 + 2 + 3) = 7, which is the minimum of all possible paths.

In the second test case, the minimum cost path will be (0, 0) -> (1, 1) -> (1, 2), So the path sum will be (2 + 2 + 1) = 5, which is the minimum of any possible path.
Sample Input 2:
2
1 3
2 1 3
2 2
1 2
-5 3
Sample Output 2:
6
-1
Explanation for sample input 2:
In the first test case, there is only one possible path which is (0, 0) -> (0, 1) -> (0, 1). The path sum is (2 + 1 + 3) = 6

In the second test case, the minimum cost path will be (0, 0) -> (1, 0) -> (1, 1), So the path sum will be (1 - 5 + 3) = -1, which is the minimum of any possible path.
Hint

Can you think about exploring all possible paths?

Approaches (3)
Recursive Brute Force

The basic idea is to explore all possible paths recursively and return the minimum path sum among them. Steps are as follows:

  1. Start exploring the path from the top left corner (0, 0).
  2. Let us assume that we are currently at (row, col)th cell. If this cell is outside the boundary of the matrix, then return infinite(a very large number) because we don’t want to include the current cell into our path.
  3. If the current cell is (N-1, M-1)th cell then return the value of the current cell. Else for the rest of the cells,
  4. There are three options possible for the next move
    • (row, col+1)th cell
    • (row+1, col)th cell
    • (row+1, col+1)th cell
  5. Break the primary problem into three subproblems which are finding minimum path sum from the cells mentioned above.
  6. Now, among the above three paths, find the path which has the minimum sum. And whatever solution we will get from the above three problems. We will take a minimum of them and the sum of cost[row][col], which will be the minimum path cost to reach (N-1, M-1) from (row, col).
  7. Repeat the whole process recursively.

The approach mentioned above can be formalised in the following manner.

Let minPathSum(row, col) is a function which returns the minimum path sum which can be obtained while moving from (row, col) to (N-1, M-1).

minPathSum(row, col) = min( minPathSum(row+1, col), minPathSum(row, col+1), minPathSum(row+1, col+1) ) + cost[row][col]
Time Complexity

O( 3^(N*M) ), where ‘N’ is the number of rows and ‘M’ is the number of columns in the given cost matrix.

We are exploring all the possible paths from (0, 0) to (N-1, M-1). From any cell, we have at maximum three possible cells to consider as our next cell in the path. And since there are N*M cells in the matrix which need to be considered. The overall complexity will be O(3^(N*M)).

Space Complexity

O(N + M), where ‘N’ is the number of rows and ‘M’ is the number of columns in the given cost matrix.

For reaching (N-1, M-1)th cell from (0, 0)th cell, we will have to traverse at max N+M-1 cells.

And since the path will be stored in the recursive call stack, the space complexity will be O(N + M).

Code Solution
(100% EXP penalty)
Min Cost Path
Full screen
Console