Find the minimum cost to reach destination using a train
There are ‘N’ stations on the route of a train. The train goes from station 0 to ‘N’ - 1. The ticket cost for all pairs of stations (i, j) is given where ‘j’ is greater than ‘i’. Your task is to find the minimum cost to reach the Nth station.

Note:

Cost of entries where j

Question

Find the minimum cost to reach destination using a train

There are ‘N’ stations on the route of a train. The train goes from station 0 to ‘N’ - 1. The ticket cost for all pairs of stations (i, j) is given where ‘j’ is greater than ‘i’. Your task is to find the minimum cost to reach the Nth station.

Note:

Cost of entries where j < i  will be represented as INT_MAX VALUE which is 10000 in the price matrix.

Example:

If ‘N’ = 3

'PRICE[3][3]' = {{0, 15, 80,},
               {INF, 0, 40},
               {INF, INF, 0}};

First, go from 1st station to 2nd at 15 costs, then go from 2nd to 3rd at 40. 15 + 40 = 55 is the total cost.It is cheaper than going directly from station 1 to station 3 as it would have cost 80.

The output will be 55.

Input format :

The first line of input contains an integer 'T' denoting the number of test cases. 

The first line of each test case contains a single integer 'N', Where ‘N’ is the number of rows and columns in the ‘PRICE’ matrix.

The next ‘N’ lines is as follows: Each line contains ‘N’ space-separated integers representing the cost of pairs (i,j) where ‘i’ and ‘j’ are indices of the matrix ‘PRICE’.

Output format :

For each test case, return the minimum price that will have to be paid such that the train reaches from 1st to 'N'th station.

Print the output for each test case in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 100
1 <= N <= 1000

Time Limit: 1 sec

Accepted Answer

The solution is to use DP and create a 2D table and fill the table using above given recursive formula.
minCost(0, N-1) = MIN { cost[0][n-1], cost[0][1] + minCost(1, N-1), ........, minCost(0, N-2) + cost[N-2][n-1] }
The extra space required in this solution would be O(N2) and time complexity would be O(N3).
This solution was accepted however, solution using recursion wasn't because time limit exceeded.

Accepted Answer

Floyd Warshall Algorithm

The idea is to calculate the minimum price between all pair of stations using Floyd Warshall Algorithm:

Pick all vertices and update all minimum-cost-paths that include the selected station as an intermediate station in the minimum-cost-path.
When we pick vertex number ‘K’ as an intermediate station, we already have considered vertices {0, 1, 2, .. ‘K’ - 1} as intermediate vertices. For every pair ('i', ‘j’) of the source station and destination station, respectively, there are two possible cases.
- ‘K’ is not an intermediate station in the minimum-cost-path from ‘i’ to ‘j’. We keep the value of ‘DIST[i][j]’ as it is.
- ‘K’ is an intermediate station in the minimum-cost-path from i to j. We update the value of ‘DIST[i][j]' as ‘DIST[i][K]' + ‘DIST[K][j]' if ‘DIST[i][j]' > ‘DIST[i][K]' + ‘DIST[K][j]'.
Then return the ‘DIST[0]['N' - 1]' because that stores the minimum cost to travel from source to destination.

Space Complexity: O(n^2)Explanation:

O(N ^ 2), Where ‘N’ is the number of rows and columns of the matrix.

Since we are using an extra 2-D matrix to keep track of the minimum-cost-path for each station. Thus the space complexity will be O(N ^ 2).

Time Complexity: O(n^3)Explanation:

O(N ^ 3), Where ‘N’ is the number of rows and columns of the matrix.

Since we have to traverse the 2-D matrix completely N times. Thus, the time complexity will be O(N ^ 3).

C++ (g++ 5.4)

/*
	Time Complexity : O(N ^ 3)
	Space Complexity : O(N ^ 2)

	Where 'N' is the number of rows and columns.
*/

int minCost(vector> &graph, int n) {
	// Creating the Distance matrix.
	vector> dist(n, vector(n)) ;
	/*
	  Initialize the solution matrix same
	  as input graph matrix.
	*/
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			dist[i][j] = graph[i][j];
		}
	}

	// Add all vertices one by one to the set of intermediate vertices.
	for (int k = 0; k < n; k++){
		/*
		  Before start of an iteration,we have shortest distances between all
	 	  pairs of vertices such that the shortest distances consider only the
		  vertices in set {0, 1, 2, .. k-1} as intermediate vertices.
		*/
		for (int start = 0; start < n; start++){
			/*
			  After the end of an iteration,vertex no. k is added to the set of
			  intermediate vertices and the set becomes {0, 1, 2, .. k}.
			*/
			for (int end = 0; end < n; end++){
				if (dist[start][k] + dist[k][end] < dist[start][end]) {
					dist[start][end] = dist[start][k] + dist[k][end];
				}
			}
		}
	}
	return dist[0][n - 1];
}

Python (3.5)

"""
	Time Complexity : O(N ^ 3)
	Space Complexity : O(N ^ 2)

	Where 'N' is the number of rows and columns.
"""

def minCost(graph, n):
	# Creating the Distance matrix.
	dist = [[0 for j in range(n)] for i in range(n)]
	"""
	  Initialize the solution matrix same
	  as input graph matrix.
	"""
	for i in range(n):
		for j in range(n):
			dist[i][j] = graph[i][j]

	# Add all vertices one by one to the set of intermediate vertices.
	for k in range(n):
		"""
		  Before start of an iteration,we have shortest distances between all
	 	  pairs of vertices such that the shortest distances consider only the
		  vertices in set :0, 1, 2, .. k-1} as intermediate vertices.
		"""
		for start in range(n):
			"""
			  After the end of an iteration,vertex no. k is added to the set of
			  intermediate vertices and the set becomes :0, 1, 2, .. k}.
			"""
			for end in range(n):
				if (dist[start][k] + dist[k][end] < dist[start][end]):
					dist[start][end] = dist[start][k] + dist[k][end]
				
	return dist[0][n - 1]

Java (SE 1.8)

/*
	Time Complexity : O(N ^ 3)
	Space Complexity : O(N ^ 2)

	Where 'N' is the number of rows and columns.
*/

import java.util.ArrayList;

public class Solution {
	public static int minCost(ArrayList> graph, int n) {
		// Creating the Distance matrix.
		ArrayList> dist = new ArrayList<>();

		// Initialize the solution matrix same as input graph matrix.
		for (int i = 0; i < n; i++) {
			dist.add(graph.get(i));
		}

		// Add all vertices one by one to the set of intermediate vertices.
		for (int k = 0; k < n; k++) {
			/*
			   Before start of an iteration,we have shortest distances between all pairs of
			   vertices such that the shortest distances consider only the vertices in set
			   {0, 1, 2, .. k-1} as intermediate vertices.
			*/
			for (int start = 0; start < n; start++) {
				/*
				   After the end of an iteration,vertex no. k is added to the set of
				   intermediate vertices and the set becomes {0, 1, 2, .. k}.
				*/
				for (int end = 0; end < n; end++) {
					if (dist.get(start).get(k) + dist.get(k).get(end) < dist.get(start).get(end)) {
						dist.get(start).set(end, dist.get(start).get(k) + dist.get(k).get(end));
					}
				}
			}
		}
		return dist.get(0).get(n - 1);
	}
}

Accepted Answer

Topological Sort on Directed Acyclic Graph(DAG)

The idea is based on the fact that the given input matrix is a Directed Acyclic Graph (DAG) because we can go from a smaller station to another and not the other way around hence DAG. The shortest path in DAG can be calculated using topological sorting.

Calculate min cost for station 1, then for station 2, etc. These costs are stored in an array ‘DIST[0…'N' - 1]'.
The min cost for station 0 is 0, i.e., ‘DIST[0]' = 0.
The min cost for station 1 is cost[0][1], i.e., ‘DIST[1]' = cost[0][1]
The min cost for station 2 is the minimum of the following two.
- ‘DIST[0]' + cost[0][2]
- ‘DIST[1]' + cost[1][2]
The min cost for station 3 is the minimum of the following three.
- ‘DIST[0]' + cost[0][3]
- ‘DIST[1]' + cost[1][3]
- ‘DIST[2]' + cost[2][3]
Similarly, ‘DIST[4]', ‘DIST[5]', … ‘DIST['N' - 1]' are calculated.
Hence after all iterations, our answer will get stored at the ‘N’th block, therefore, return it.

Space Complexity: O(n)Explanation:

O(N), Where ‘N’ is the number of rows and columns of the matrix.

Since we are using an extra array to keep track of the minimum-cost-path for each station.

Time Complexity: O(n^2)Explanation:

O(N ^ 2), Where ‘N’ is the number of rows and columns of the matrix.

Since we have to traverse the 2-D matrix completely. Thus the time complexity will be O(N ^ 2).

Python (3.5)

"""
	Time Complexity : O(N ^ 2)
	Space Complexity : O(N)

	Where 'N' is the number of rows and columns.
"""

def minCost(graph, n):
	"""
	  Distance array to store the minimum distance.
	  Initialize the array with maximum value.
	"""
	dist = [100000 for i in range(n)]
	dist[0] = 0

	# Go through every station and check if using it as an intermediate station gives better path.
	for i in range(n):
		for j in range(i + 1, n):
			if (dist[j] > dist[i] + graph[i][j]):
				dist[j] = dist[i] + graph[i][j]
			
	return dist[n - 1]

Java (SE 1.8)

/*
	Time Complexity : O(N ^ 2)
	Space Complexity : O(N)

	Where 'N' is the number of rows and colomns.
*/

import java.util.ArrayList;

public class Solution {
	public static int minCost(ArrayList> graph, int n) {
		// Distance array to store the minimum distance.
		int[] dist = new int[n];

		// Initialize the array with maximum value.
		for (int i = 0; i < n; i++) {
			dist[i] = 100000;
		}
		dist[0] = 0;

		/*
		   Go through every station and check if using it as an intermediate station
		   gives better path.
		*/
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				if (dist[j] > dist[i] + graph.get(i).get(j)) {
					dist[j] = dist[i] + graph.get(i).get(j);
				}
			}
		}

		return dist[n - 1];
	}
}

C++ (g++ 5.4)

/*
	Time Complexity : O(N ^ 2)
	Space Complexity : O(N)

	Where 'N' is the number of rows and columns.
*/

int minCost(vector> &graph, int n){
	// Distance array to store the minimum distance.
	int dist[n];

	// Initialize the array with maximum value. 
	for (int i = 0; i < n; i++) {
		dist[i] = 1e5;
	}
	dist[0] = 0;

	// Go through every station and check if using it as an intermediate station gives better path.
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (dist[j] > dist[i] + graph[i][j]) {
				dist[j] = dist[i] + graph[i][j];
			}
		}
	}

	return dist[n - 1];
}

There are ‘N’ stations on the route of a train. The train goes from station 0 to ‘N’ - 1. The ticket cost for all pairs of stations (i, j) is given where ‘j’ is greater than ‘i’. Your task is to find the minimum cost to reach the Nth station.

Note:

Example:

Input format :

Output format :

Note:

Constraints:

Top Deutsche Bank Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern

Top HR questions asked in Deutsche Bank Software Developer Intern