Home » Interview coding problems/challenges

Minimum Path Sum

Solution of the Minimum Path Sum problem – this is a very popular coding problem, with some variations in the conditions the problem has been featured in interview rounds of many big companies such as Goldman Sachs, Amazon, Tower Research and others.
Submitted by Divyansh Jaipuriyar, on April 30, 2020

Problem statement

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

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

Input

Input starts with an integer T (≤ 100), denoting the number of test cases. Each case starts with an integer m and n (1 ≤ n,m ≤ 1000) denoting the number of rows and number of columns, followed by m rows having n columns as input.

Output

Output the minimum sum to reach the end.

Explanation with example

    Input: 
    T = 1
    m = 3, n = 3
    [1,3,1]
    [1,5,1]
    [4,2,1]

    Output: 
    7
    Because the path 1→3→1→1→1 minimizes the sum.

Solution Approach

1) Using dynamic programming

We will create a cost[m][n] matrix for storing the cost of visiting the cell, visiting the grid[0][0] will cost the same, visiting the cell at the first row will only consider the cost of visiting the current cell cost plus the upto the last visited cell that is cost[0][j]=cost[0][j-1]+grid[0][j], similarly the cost of visiting the last column will cost the current grid value plus the cost upto the cell before it that it cost[i][0]=cost[i-1][0]+grid[i][0] and the rest of the cell will cost the min of cost coming from left or cost coming from top that is cost[i][j]=min(cost[i][j-1],cost[i-1][j])+grid[i][j]

Pseudo Code

int findsum(grid[m][n])
	if(m==0 and n==0)
		return 0
	else
		for(row=0;row<m;row++)
			for(col=0;col>n;col++)
				if(row==0 and col==0)
					cost[row][col]=grid[row][col]
				if(row==0)
					cost[row][col]=cost[row][col-1]+grid[row][col]
				if(col==0)
					cost[row][col]=cost[row-1][col]+grid[row][col]
				else
					cost[row][col]=min(cost[row-1][col],cost[row][col-1])+grid[row][col]

Time Complexity: O(m*n)

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main()
{
    ll t;
    cout << "Enter number of test case: ";
    cin >> t;

    while (t--) {
        ll m, n;

        cout << "Enter number of rows and columns: ";
        cin >> m >> n;

        ll dp[m][n], dp1[m][n];

        cout << "Enter elements: ";
        for (ll i = 0; i < m; i++)
            for (ll j = 0; j < n; j++)
                cin >> dp[i][j];

        for (ll i = 0; i < m; i++) {
            for (ll j = 0; j < n; j++) {
                if (i == 0 and j == 0)
                    dp1[i][j] = dp[i][j];
                else if (i == 0 and j != 0)
                    dp1[i][j] = dp1[i][j - 1] + dp[i][j];
                else if (j == 0 and i != 0)
                    dp1[i][j] = dp1[i - 1][j] + dp[i][j];
                else
                    dp1[i][j] = min(dp1[i - 1][j], dp1[i][j - 1]) + dp[i][j];
            }
        }
        
        cout << "Minimum Cost: ";
        cout << dp1[m - 1][n - 1] << "\n";
    }
    return 0;
}

Output

Enter number of test case: 2
Enter number of rows and columns: 3 3
Enter elements: 1 3 1
1 5 1
4 2 1
Minimum Cost: 7
Enter number of rows and columns: 4 4
Enter elements: 1 3 5 2
3 4 7 2
4 5 2 8
4 5 9 1
Minimum Cost: 22

2) Using graphical approach

Initially, we will declare the cost of visiting the cell as INFINITE then

we will use relaxation principal, that is if the cost of visiting the cell plus the distance of the previous cell is smaller than the current cell cost we will update the cost and we keep on doing it until we get the minimum cost.

we will use queue with pair to use the index of visited cell or unvisited cell, similar to level order traversal approach.

Pseudo Code

findsum(grid[m][n])
	cost[m][n]
	for(row=0;row<m;row++)
		for(col=0;col<n;col++)
			cost[row][col]=INFINTE
		
	cost[0][0]=grid[0]][0]
	queue<pair<int,int>> q
	q.push({0,0})
	dx[]={0,1}
	dy[]={1,0}
		
	while(!q.empty())
	{
		pair<int,int> p=q.front()
		q.pop()
		x=p.first
		y=p.second
		for(i=0;i<2;i++)
		{
			a=x+dx[i],b=y+dy[i]
			if(a>=0 and a<m and b>=0 and b<n and cost[a][b]>cost[x][y]+grid[a][b])
			{
				q.push({a,b})
			cost[a][b]=cost[x][y]+grid[a][b]
			}
		}
	}

Time Complexity: O(n*m)

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main()
{
    ll t;
    cout << "Enter the number of test cases: ";
    cin >> t;

    while (t--) {
        cout << "Enter numbe of rows and columns: ";
        ll n, m;
        cin >> n >> m;

        ll grid[n][m];
        ll cost[n][m];

        cout << "Enter elements: ";
        for (ll i = 0; i < n; i++)
            for (ll j = 0; j < m; j++) {
                cin >> grid[i][j];
                cost[i][j] = INT_MAX;
            }

        cost[0][0] = grid[0][0];
        queue<pair<ll, ll> > q;
        q.push({ 0, 0 });
        ll dx[] = { 0, 1 };
        ll dy[] = { 1, 0 };

        while (!q.empty()) {
            pair<ll, ll> p = q.front();
            q.pop();
            ll x = p.first;
            ll y = p.second;
            for (ll j = 0; j < 2; j++) {
                ll u = x + dx[j];
                ll v = y + dy[j];
                if (u >= 0 and u < n and v >= 0 and v < m and cost[u][v] > cost[x][y] + grid[u][v]) {
                    cost[u][v] = cost[x][y] + grid[u][v];
                    q.push({ u, v });
                }
            }
        }

        cout << "Minimum Cost: ";
        cout << cost[n - 1][m - 1] << "\n";
    }
    return 0;
}

Output

Enter number of test case: 2
Enter number of rows and columns: 3 3
Enter elements: 1 3 1
1 5 1
4 2 1
Minimum Cost: 7
Enter number of rows and columns: 4 4
Enter elements: 1 3 5 2
3 4 7 2
4 5 2 8
4 5 9 1
Minimum Cost: 22

Reference: https://leetcode.com/problems/minimum-path-sum/