Minimum Path Sum

Difficulty Level Medium
Frequently asked in Amazon Bloomberg Facebook Goldman Sachs Google Microsoft
Array Dynamic ProgrammingViews 3370

In the minimum path sum problem, we have given “a × b” matrix consisting of non-negative numbers. Your task is to find the path from top left to right bottom which minimizes the sum consisting of all the numbers which come in a path you found.

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

Example

Input

[1,0,2],
[2,0,5],
[1,0,1]

Output

2

Explanation

Because it follows the path 1→0→0→0→1, which minimizes the sum as 2.

Minimum Path Sum

This image shows the path followed to reach from top left to bottom right

Input

[1,3,1],
[1,5,1],
[4,2,1]

Output

7

Explanation

Because it follows the path 1→3→1→1→1, which minimizes the sum as 7.

Minimum Path Sum

This image shows the path followed from the top left to reach bottom right.

Algorithm for Minimum Path Sum

Now we understand the problem statement of minimum path sum. Without discussing much we just move to the algorithm used for the implementation of this problem.

  1. Get the input value in an array.
  2. Open a nested for loop and make it run until all the rows and columns traverse of the given input array.
    1. If i = =0 &&j = =0
      • then continue, means leave this iteration and jump onto next one.
    2. Else if i = =0
      • then array[i][j]=array[i][j]+ arr[i][j-1];
    3. Else if j = =0
      • arr[i][j] = arr[i][j] + arr[i-1][j];
    4. Else
      • arr[i][j] = getMin(arr[i-1][j]+arr[i][j], arr[i][j-1]+arr[i][j])
    5. Pass these values to getMin function which returns the minimum value between two.
  3. Return array[rows-1][columns-1];

Explanation

In minimum path sum problem, our job is to find that path in a matrix that minimizes the sum consisting of all the integers which come in the path, so we need to declare a function where the function is defined as to return the smallest value between the two values which are passed on to that function.

So now, we start a nested for loop, make the outer loop run-up to the value (row -1) is reached, and the inner loop up to column -1 is reached.

Step by Step Execution

So now let us take an example to understand minimum path sum problem,

Input : {{1,3,4},

{2,0,2},

{2,0,1}};

For  now,

  • i=0, j=0

If part executes and it will continue and jump onto the next one.

  • i=0, j=1

else if ( i = = 0 ) executes and arr[i][j] = arr [i][j] + arr [i][j-1]

means arr[0][1]= 3+1 = 4

  • i=0, j=2

else if ( i = = 0 ) executes and arr[i][j] = arr [i][j] + arr [i][j-1]

means arr[0][2]= arr[0][2]  + arr [0][1] = 4 +1 =5

  • i=1,j=0

else if ( j = = 0 ) executes and arr[i][j] = arr [i][j] + arr [i-1][j]

means arr[1][0]= arr[1][0]  + arr [0][0] = 2 +1 =3

  • i=1,j=1

else part executes and getMin( arr[i-1][j] + arr [i][j],  arr [i][j-1] + arr[i][j] ) function is call

and getMin( arr[0][1]) + arr[1][1], arr[1][0]+arr[1][1]) = ( 1 + 2, 3+2)

which will return the smallest value is 3 in arr[1][1] => arr[1][1]=3

  • i=1,j=2

else part executes and getMin( arr[i-1][j] + arr [i][j],  arr [i][j-1] + arr[i][j] ) function is call

and getMin( arr[0][2]) + arr[1][2], arr[1][1]+arr[1][2]) = ( 5 + 2, 3+2)

which will return the smallest value is 5 in arr[1][2] => arr[1][2]=5.

arr[1][2]=5.

  • i=2,j=0

else if ( j = = 0 ) executes and arr[i][j] = arr [i][j] + arr [i-1][j]

means arr[2][0]= arr[2][0]  + arr [1][0] = 2 +2 =4

arr[2][2]=4.

  • i=2,j=1

else part executes and getMin( arr[i-1][j] + arr [i][j],  arr [i][j-1] + arr[i][j] ) function is call

and getMin( arr[1][1]) + arr[2][1],  arr[2][0]+arr[2][1]) = ( 3+0, 4+0)

which will return the smallest value is 3 in arr[2][1] => arr[2][1]=3.

arr[1][2]=3.

  • i=2,j=2

else part executes and getMin( arr[i-1][j] + arr [i][j],  arr [i][j-1] + arr[i][j] ) function is call

and getMin( arr[1][2]) + arr[2][2], arr[2][1]+arr[2][2]) = ( 5 + 1, 3+1)

which will return the smallest value is 4 in arr[2][2] => arr[2][2]=5.

arr[2][2]=4.

And it will return the arr[2][2] which is 4 and that is our output value which defines the minimum sum path.

Output: 4

C++ Program for Minimum Path Sum

#include<iostream>
using namespace std;

int getMin(int val1, int val2)
{
    return val1 < val2 ? val1 : val2;
}
int getMinimumSum(int arr[3][3])
{
    for(int i=0; i<3; i++)
    {
        for(int j=0; j<3; j++)
        {
            if(i==0 && j == 0)
            {
                continue;
            }
            else if(i==0)
            {
                arr[i][j] = arr[i][j] + arr[i][j-1];
            }
            else if(j==0)
            {
                arr[i][j] = arr[i][j] + arr[i-1][j];
            }
            else
            {
                arr[i][j] = getMin(arr[i-1][j]+arr[i][j], arr[i][j-1]+arr[i][j]);
            }
        }
    }
    return arr[2][2];
}
int main()
{
    int inputArray[3][3] = {{1,3,4},
                            {2,0,2},
                            {2,0,1}};
                            
    cout<<"Length of minimum path sum: "<<getMinimumSum(inputArray);
    return 0;
}
Length of minimum path sum: 4

Java Program for Minimum Path Sum

class MinimumPathSum {
  private static int getMin(int val1, int val2) {
    return val1<val2 ? val1 : val2;
  }
  private static int getMinimumSum(int[][] arr) {
    for (int i = 0; i<arr.length; i++) {
      for (int j = 0; j<arr[i].length; j++) {
        if (i == 0 && j == 0) {
          continue;
        } else if (i == 0) {
          arr[i][j] = arr[i][j] + arr[i][j - 1];
        } else if (j == 0) {
          arr[i][j] = arr[i][j] + arr[i - 1][j];
        } else {
          arr[i][j] = getMin(arr[i - 1][j] + arr[i][j], arr[i][j - 1] + arr[i][j]);
        }
      }
    }
    int r = arr.length - 1;
    int c = arr[0].length - 1;
    return arr[r][c];
  }
  public static void main(String[] args) {
    int[][] inputArray = {{1, 3, 4},
                {2, 0, 2},
                {2, 0, 1}};

    System.out.println("Length of minimum path sum: " + getMinimumSum(inputArray));
  }
}
Length of minimum path sum: 4

Complexity Analysis for Minimum Path Sum

Time Complexity

O(m*n) where “m” and “n” are the numbers of rows and columns in the matrix given in the minimum path sum problem.

Space Complexity

O(1) because we don’t use any auxiliary space while implement the approach for minimum path sum.

References

Translate »