Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Minimum Path Sum

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

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
All tags
Sort by
Search icon

Interview problems

C++ || DP Solution || Optimal Solution || Tabulation

#include <bits/stdc++.h> 

int minSumPath(vector<vector<int>> &grid) {

    int n = grid.size();

        int m = grid[0].size();

        vector<int> dp(m,0);

 

        for(int i=0; i<n; i++) {

            vector<int> temp(m,0);

            for(int j=0; j<m; j++) {

                if(i == 0 && j==0) temp[j] = grid[i][j];

                else {

                    int up = grid[i][j];

                    int left = grid[i][j];

                    

                    if(i > 0) up += dp[j]; 

                    else up = 1e9; 

                    

                    if(j > 0) left += temp[j-1]; 

                    else left = 1e9; 

                    

                    temp[j] = min(up,left);

                }

            }

            dp = temp;

        }

        return dp[m-1];

}

18 views
0 replies
0 upvotes

Interview problems

C++ || DP||Memoization

#include <bits/stdc++.h> 
int code(int i ,int j ,int n ,int m ,vector<vector<int>> &dp,vector<vector<int>> &mat)
{
   
if(i==n-1 && j==m-1) return  mat[i][j];
if(dp[i][j] != -1) return dp[i][j];
int right =INT_MAX;int down = INT_MAX;
if(j<m-1)
right = mat[i][j] + code(i,j+1,n,m,dp,mat);
if(i<n-1)
down = mat[i][j] + code(i+1,j,n,m,dp,mat);
return dp[i][j] = min(right,down);
}
int minSumPath(vector<vector<int>> &mat) {
    // Write your code here.
    int n = mat.size();
        int m = mat[0].size();
          std::vector<std::vector<int>> dp(n, std::vector<int>(m, -1)); 
          return code(0,0,n,m,dp,mat);
}
24 views
0 replies
0 upvotes

Interview problems

Java Solution

Recursion

import java.util.* ;
import java.io.*; 
public class Solution {

    public static int findCost(int [][] grid,int i,int j){
        if(i==0 && j==0){
            return grid[i][j];
        }
        if(i<0 || j<0){
            return Integer.MAX_VALUE;
        }
        int up=findCost(grid, i-1, j);
        int left=findCost(grid, i, j-1);

        return grid[i][j]+Math.min(up,left);
    }
    public static int minSumPath(int[][] grid) {
    	// Write your code here.
        return findCost(grid,grid.length-1,grid[0].length-1);
    }
}

 

Memoization

import java.util.* ;
import java.io.*; 
public class Solution {

    public static int findCost(int [][] grid,int i,int j){
        if(i==0 && j==0){
            return grid[i][j];
        }
        if(i<0 || j<0){
            return Integer.MAX_VALUE;
        }
        int up=Integer.MAX_VALUE;
        if(i>0)
        up=grid[i][j]+findCost(grid, i-1, j);
        int left=Integer.MAX_VALUE;
        if(j>0)
        left=grid[i][j]+findCost(grid, i, j-1);

        return Math.min(up,left);
    }
    public static int minSumPath(int[][] grid) {
    	// Write your code here.
        return findCost(grid,grid.length-1,grid[0].length-1);
    }
}

 

Tabulation 

import java.util.* ;
import java.io.*; 
public class Solution {

    public static int findCost(int [][] grid,int [][] dp,int i,int j){
        if(i==0 && j==0){
            return dp[i][j]=grid[i][j];
        }
        if(i<0 || j<0){
            return Integer.MAX_VALUE;
        }
        if(dp[i][j]!=-1){
            return dp[i][j];
        }
        int up=Integer.MAX_VALUE;
        if(i>0)
        up=grid[i][j]+findCost(grid,dp, i-1, j);
        int left=Integer.MAX_VALUE;
        if(j>0)
        left=grid[i][j]+findCost(grid,dp, i, j-1);

        return dp[i][j]=Math.min(up,left);
    }
    public static int minSumPath(int[][] grid) {
    	// Write your code here.
        int m=grid.length;
        int n=grid[0].length;
        int dp[][]=new int [m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                dp[i][j]=-1;
            }
        }
        return findCost(grid,dp,m-1,n-1);
    }
}
19 views
0 replies
0 upvotes

Interview problems

easy cpp DP|| memoization

#include <bits/stdc++.h> 

using namespace std;

    long mini(int m,int n,vector<vector<int>>& grid,vector<vector<int>> &dp){

        if(m==0 && n==0) return grid[0][0];

        if(m<0 || n<0) return INT_MAX;

        if(dp[m][n]!=-1) return dp[m][n];

        long up=grid[m][n]+mini(m-1,n,grid,dp); 

        long left=grid[m][n]+mini(m,n-1,grid,dp); 

        return dp[m][n]=min(up,left);

    }

    

int minSumPath(vector<vector<int>> &grid) {

    // Write your code here.

    int m=grid.size();

        int n=grid[0].size();

        vector<vector<int>> dp(m,vector<int>(n,-1));

        return mini(m-1,n-1,grid,dp);

}

54 views
0 replies
0 upvotes

Interview problems

JAVA-DP-Memoization

import java.util.* ;

import java.io.*; 

public class Solution {

    static int findMin(int i,int j,int[][] grid,int[][] dp)

    {

        if (i == 0 && j == 0) {

            return dp[i][j]=grid[i][j];

        }

        if (i < 0 || j < 0) {

            return 22222222;

        }

        if (dp[i][j] != -1) {

            return dp[i][j];

        }

        

        int up = grid[i][j] + findMin(i - 1, j, grid, dp);

        int left = grid[i][j] + findMin(i, j - 1, grid, dp);

        

        return dp[i][j] = Math.min(up, left);

    }

    public static int minSumPath(int[][] grid) {

        // Write your code here.

        int n=grid.length;

        int m=grid[0].length;

        int[][] dp=new int[n+1][m+1];

        for(int[] row:dp)

        {

            Arrays.fill(row,-1);

        }

        return findMin(n-1,m-1,grid,dp);

    }

}

12 views
0 replies
0 upvotes

Interview problems

EASY JAVA SOLUTION

public static int minSumPath(int[][] grid) {
        int N = grid.length;
        int M = grid[0].length;

        int dp [][] = new int[N][M];

        dp[0][0]= grid[0][0];

        for (int j = 1; j < M; j++) {
            dp[0][j] = dp[0][j-1] + grid[0][j]; 
        }

        for (int i = 1; i < N; i++) {
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }

        for (int i = 1; i < N; i++) {
            for (int j = 1; j < M; j++) {
                dp[i][j] = grid[i][j] + Math.min(dp[i-1][j], dp[i][j-1]);
            }
        }
        return dp[N-1][M-1];
    }
48 views
0 replies
0 upvotes

Interview problems

All test case passed || Easy solution || Take sum from up and left || o(n2) dp

So u will start with taking the sum in column and row , prev + the index 

then after you will start filling your dp table where dp[i][j] will be the addition of the current index + min(dp[i-1],[j], dp[i][j-1]) (left and above) both the approach is taken care of 

 

heres the code:

 

 

#include <bits/stdc++.h> 

int minSumPath(vector<vector<int>> &grid) {

    int n = grid.size();

    int m = grid[0].size();

    

   

    vector<vector<int>> dp(n, vector<int>(m, 0));

    dp[0][0] = grid[0][0];

 

    for (int i = 1; i < m; i++) {

        dp[0][i] = dp[0][i - 1] + grid[0][i];

    }

    

    

    for (int i = 1; i < n; i++) {

        dp[i][0] = dp[i - 1][0] + grid[i][0];

    }

    

    for (int i = 1; i < n; i++) {

        for (int j = 1; j < m; j++) {

            dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1]);

        }

    }

    

    return dp[n - 1][m - 1];

}

 

54 views
0 replies
0 upvotes

Interview problems

My simple dp solution with Comments

#include <bits/stdc++.h> 

int minSumPath(vector<vector<int>> &grid) {

    int n = grid.size(), m = grid[0].size();

 

        vector<vector<int>> dp(n, vector<int> (m, 0)); //State of dp --> dp[i][j] -> min sum path from (0,0) to (i,j)

        //base case

        dp[0][0] = grid[0][0];

        for(int i=1;i<m;i++){     //initialization of 1st row

            dp[0][i] = grid[0][i] + dp[0][i-1];

        }

        for(int i=1;i<n;i++){     //initialization of 1st col

            dp[i][0] = grid[i][0] + dp[i-1][0];

        }

 

        for(int i=1;i<n;i++){

            for(int j=1;j<m;j++){

                dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]);  //Transition Equation

            }

        }

        

        return dp[n-1][m-1];  // final subproblem ans

}

86 views
0 replies
0 upvotes

Interview problems

C++ most optimised O(N^2) : DP solution

#include <bits/stdc++.h> 
// dp memoisation
int solve(vector<vector<int>> &grid,int i,int j,vector<vector<int>> &dp){
    if(i == 0 && j == 0){
        return grid[0][0];
    }
    if(i <0 || j < 0){
        return  1e9 + 7; 
    }
    if(dp[i][j] != -1){
        return dp[i][j];
    }
    int up = grid[i][j] + solve(grid,i-1,j,dp);
    int left = grid[i][j] + solve(grid,i,j-1,dp);
    return dp[i][j] = min(left,up);
}
int minSumPath(vector<vector<int>> &grid) {
    // Write your code here.
    int n = grid.size();
    int m = grid[0].size();
    vector<vector<int>> dp(n,vector<int>(m,0));
    for(int i =0;i < n;i++){
        for(int j = 0; j < m; j++){
             if(i == 0 && j == 0){
                dp[i][j] = grid[0][0];
            }
            else{
                int up = grid[i][j];
                if (i > 0) {
                    up += dp[i - 1][j];
                }
                else{
                    up += 1e9;
                }
                int left = grid[i][j];
                if (j > 0) {
                    left += dp[i][j-1];
                } else {
                    left += 1e9;
                }
                dp[i][j] = min(left, up);
            }
        }
    }
    return dp[n-1][m-1];
}
158 views
0 replies
0 upvotes

Interview problems

c++ || recursion || recursion + memoization

  1. method 1

 

#include <bits/stdc++.h> 

int solve( int n, int m, vector<vector<int>> &grid)

{

    if(n==0 && m==0)

    {

        return grid[0][0];

    }

    if( n<0 || m<0)

    {

        return 1e9 + 7;

    }

 

    int up= solve(n-1,m,grid)+grid[n][m];

    int left=solve(n,m-1,grid)+grid[n][m];

 

    return min( up, left);

}

 

int minSumPath(vector<vector<int>> &grid) 

{

    // Write your code here.

    int n=grid.size();

    int m=grid[0].size();

 

    return solve( n-1,m-1,grid);

}

 

method 2

 

190 views
0 replies
1 upvote
Full screen
Console