2361. Minimum Costs Using the Train Line
Problem Description
Imagine you're in a city with a train system that has two different types of routes, the regular and express routes, covering the same series of stops from stop 0 to stop n. Each segment between two consecutive stops has a cost associated with it, depending on which route you take: the cost is outlined in two arrays, regular
for the regular route and express
for the express route.
While on the regular route, if you decide to switch to the express route, it incurs an additional cost, specified by the expressCost
. However, transferring back to the regular route from the express route doesn't cost anything. Also, whenever you decide to switch to the express route, you have to pay the expressCost
every single time.
The goal is to calculate the minimum cost to reach each stop from stop 0 by possibly switching between routes strategically to minimize your total cost. The output should be an array representing the minimum cost to reach each stop, starting from stop 1 up to stop n (1-indexed).
Intuition
To find the minimum cost to reach each stop, it's necessary to track the cost of two scenarios at any stop: staying on the regular route, and being on the express route. At each stop, you can stay on the current route or transfer to the other one (with the possibility of an additional expressCost
if switching to the express route).
We begin by initializing two variables, f
and g
:
f
represents the minimum cost of reaching the current stop via the regular route.g
represents the minimum cost of reaching the current stop via the express route.
Starting from stop 0, we iterate over each stop. For each stop, we calculate the new costs ff
and gg
.
ff
represents the new cost of reaching the next stop on the regular route. This cost is the minimum between staying on the regular route (f + a
, wherea
is the regular cost of the next segment) or switching from the express route to the regular route (g + a
, since switching back to regular is free).gg
represents the new cost of reaching the next stop on the express route. This is the minimum between switching from the regular route (f + expressCost + b
, whereb
is the express cost of the next segment) or staying on the express route (g + b
).
After calculating ff
and gg
, we update f
and g
respectively. The minimum of f
and g
is then stored in the cost array as the minimum cost to reach the current stop. This way, the process accounts for the possibility that it might be cheaper to switch to the express route or to stay on the regular route at different points along the journey.
The final array represents the least amount of money you need to spend to reach each stop, and it's built progressively as we loop through all stops.
Learn more about Dynamic Programming patterns.
Solution Approach
The solution to this problem adopts a dynamic programming approach, which is a method for efficiently solving problems that have overlapping subproblems and optimal substructure properties by breaking them down into simpler subproblems.
In this case, the optimal cost to reach a certain stop can be calculated based on the optimal costs to reach previous stops. The solution uses two variables, f
and g
, to keep track of the accumulated costs of the regular and express routes up until the current stop. These accumulate the total cost of reaching the current stop on their respective routes, considering all the previous decisions made (to switch routes or not).
The solution involves a loop that iterates through each pair of costs (a, b)
from the regular
and express
lists. Here is the breakdown of the loop's execution:
-
For each index
i
(1-indexed), we calculateff
andgg
which are the tentative costs for the next stop on the regular and express routes respectively.ff
is calculated asmin(f + a, g + a)
. Here,f + a
is the cost if we continue on the regular route, andg + a
is the cost if we transfer from the express to the regular route at this stop, which comes free of charge.gg
is calculated asmin(f + expressCost + b, g + b)
. Thef + expressCost + b
part computes the cost if we switch to the express route from the regular route, which includes theexpressCost
, andg + b
computes the cost if we keep going on the express route.
-
After calculating
ff
andgg
, the variablesf
andg
are updated with the new valuesff
andgg
respectively. This is done because we've now accumulated the cost to reach the next stop (i), and we need to keep our accumulation up to date. -
The minimum of
f
andg
at stopi
(which has become our new stopi - 1
for the next iteration of the loop) is saved into the cost array, as it represents the minimum cost to reach this stop from the start.
By using this approach, the solution iteratively builds up the minimum cost to reach each stop, considering both routes and the potential to switch between them along the way. The final cost array captures the minimum accumulated costs to reach every stop using the optimal strategy.
The algorithm assumes the inf
(infinity) value is a large enough number to represent an impossible high cost that would not be considered a minimum in any practical scenario, which is used to initialize the cost of using the express route before any stops have been reached via the express route. Moreover, the solution benefits from the use of the enumerate
function in Python, which allows iterating over both the indices and the elements of the costs lists simultaneously.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's say we have a city with 4 stops (stop 0 to stop 3), and the costs for the regular and express routes are given by regular = [1, 3, 2]
and express = [4, 1, 2]
respectively. Assume the additional cost to switch to the express route is represented by the variable expressCost = 2
. According to the problem, switching back to the regular route is free. We want to calculate the minimum cost to reach each stop from stop 0.
Initialization:
- f = 0 (cost of reaching the first stop on the regular route is always 0 since we start here)
- g = inf (we haven't reached any stops via the express route yet)
Step-by-step explanation:
-
To reach stop 1:
- Regular route:
ff = min(f + regular[0], g + regular[0]) = min(0 + 1, inf + 1) = 1
- Express route:
gg = min(f + expressCost + express[0], g + express[0]) = min(0 + 2 + 4, inf + 4) = 6
- Update f and g:
f = 1
,g = 6
. The minimum cost to reach stop 1 ismin(f, g) = 1
.
- Regular route:
-
To reach stop 2:
- Regular route:
ff = min(f + regular[1], g + regular[1]) = min(1 + 3, 6 + 3) = 4
- Express route:
gg = min(f + expressCost + express[1], g + express[1]) = min(1 + 2 + 1, 6 + 1) = 4
- Update f and g:
f = 4
,g = 4
. The minimum cost to reach stop 2 ismin(f, g) = 4
.
- Regular route:
-
To reach stop 3:
- Regular route:
ff = min(f + regular[2], g + regular[2]) = min(4 + 2, 4 + 2) = 6
- Express route:
gg = min(f + expressCost + express[2], g + express[2]) = min(4 + 2 + 2, 4 + 2) = 6
- Update f and g:
f = 6
,g = 6
. The minimum cost to reach stop 3 ismin(f, g) = 6
.
- Regular route:
Conclusion:
The final array containing the minimum costs to reach stops 1 to 3 is [1, 4, 6]
. This represents the least amount of money needed to reach each stop when choosing the optimal route at each step of the journey.
Solution Implementation
1from typing import List
2
3class Solution:
4 def minimum_costs(
5 self, regular: List[int], express: List[int], express_cost: int
6 ) -> List[int]:
7 n = len(regular) # Total number of days
8 # Initialize cost for regular and express as zero for day 0
9 regular_cost = 0
10 express_cost_total = float('inf') # Set initial express cost to infinity
11 costs = [0] * n # Initialize the list to store minimum costs for each day
12
13 # Iterate through each day's regular and express costs
14 for i, (regular_day_cost, express_day_cost) in enumerate(zip(regular, express), 1):
15 # Calculate the minimum cost to take regular path on the current day
16 min_cost_regular = min(regular_cost + regular_day_cost, express_cost_total + regular_day_cost)
17 # Calculate the minimum cost to take express path on the current day, including the express_cost
18 min_cost_express = min(regular_cost + express_cost + express_day_cost, express_cost_total + express_day_cost)
19
20 # Update the total regular and express costs to reflect today's costs
21 regular_cost, express_cost_total = min_cost_regular, min_cost_express
22
23 # Store the minimum of the two costs in the costs array
24 costs[i - 1] = min(regular_cost, express_cost_total)
25
26 return costs # Return the minimum costs for each day
27
1class Solution {
2 public long[] minimumCosts(int[] regular, int[] express, int expressCost) {
3 // Determine the number of days based on the regular array length
4 int numberOfDays = regular.length;
5
6 // f represents the minimum cost using regular routes up to day i
7 long minCostRegular = 0;
8 // g represents the minimum cost using express routes up to day i (initially set to a large number)
9 long minCostExpress = Long.MAX_VALUE / 2; // Long.MAX_VALUE / 2 to avoid overflow in future calculations
10
11 // Array to store the minimum cost for each day
12 long[] cost = new long[numberOfDays];
13
14 // Iterate through each day to find minimum costs
15 for (int i = 0; i < numberOfDays; ++i) {
16 // Cost of regular and express route for the current day i
17 int costRegular = regular[i];
18 int costExpress = express[i];
19
20 // Calculating the minimum cost if using the regular route on day i
21 long newMinCostRegular = Math.min(minCostRegular + costRegular, minCostExpress + costRegular);
22
23 // Calculating the minimum cost if using the express route on day i, with expressCost included
24 long newMinCostExpress = Math.min(minCostRegular + expressCost + costExpress, minCostExpress + costExpress);
25
26 // Update the minimum costs for regular and express
27 minCostRegular = newMinCostRegular;
28 minCostExpress = newMinCostExpress;
29
30 // Store the minimum of the two in the cost array for the day i
31 cost[i] = Math.min(minCostRegular, minCostExpress);
32 }
33
34 return cost; // Return the array containing minimum costs for each day
35 }
36}
37
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6 // Calculates the minimum costs for each station using either regular or express service.
7 vector<long long> minimumCosts(vector<int>& regular, vector<int>& express, int expressCost) {
8 int n = regular.size(); // Number of stations
9 long long costRegular = 0; // Minimum cost using regular service up to current station
10 long long costExpress = LLONG_MAX; // Minimum cost using express service up to current station, initialized with max value
11 vector<long long> minCosts(n); // Stores the minimum cost for each station
12
13 // Iterate through each station
14 for (int i = 0; i < n; ++i) {
15 int regularCost = regular[i]; // Cost of regular service at current station
16 int expressCostAtStation = express[i]; // Cost of express service at current station
17
18 // Calculate the new minimum cost of reaching the current station via regular service
19 long long newCostRegular = std::min(costRegular + regularCost, costExpress + regularCost);
20 // Calculate the new minimum cost of reaching the current station via express service
21 long long newCostExpress = std::min(costRegular + expressCost + expressCostAtStation,
22 costExpress + expressCostAtStation);
23
24 // Update the minimum costs for regular and express service at current station
25 costRegular = newCostRegular;
26 costExpress = newCostExpress;
27
28 // The minimum cost for the current station is the smaller of the two minimum costs
29 minCosts[i] = std::min(costRegular, costExpress);
30 }
31
32 return minCosts; // Return the vector of minimum costs for each station
33 }
34};
35
1function minimumCosts(regularCosts: number[], expressCosts: number[], expressLaneCost: number): number[] {
2 // The number of days
3 const numDays = regularCosts.length;
4
5 // Minimum accumulated cost using the regular lane
6 let minRegularCost = 0;
7
8 // Minimum accumulated cost using the express lane (initialized to a large number)
9 let minExpressCost = Number.MAX_SAFE_INTEGER;
10
11 // Array to store the minimum cost for each day
12 const totalCosts: number[] = new Array(numDays).fill(0);
13
14 // Iterate over each day
15 for (let day = 0; day < numDays; ++day) {
16 // Cost of using the regular lane on the current day
17 const currentRegularCost = regularCosts[day];
18
19 // Cost of using the express lane on the current day
20 const currentExpressCost = expressCosts[day];
21
22 // Compute the minimum cost for the current day using the regular lane
23 const newMinRegularCost = Math.min(minRegularCost + currentRegularCost, minExpressCost + currentRegularCost);
24
25 // Compute the minimum cost for the current day using the express lane
26 const newMinExpressCost = Math.min(minRegularCost + expressLaneCost + currentExpressCost, minExpressCost + currentExpressCost);
27
28 // Update minimum costs for both lanes
29 minRegularCost = newMinRegularCost;
30 minExpressCost = newMinExpressCost;
31
32 // Record the minimum total cost for the current day
33 totalCosts[day] = Math.min(minRegularCost, minExpressCost);
34 }
35
36 // Return the array of minimum total costs for each day
37 return totalCosts;
38}
39
Time and Space Complexity
Time Complexity
The provided code snippet goes through the lists regular
and express
exactly once, performing a constant number of operations for each element. The enumerate
function is used to iterate over both lists simultaneously, and for each element, a comparison and a few arithmetic operations are conducted. These operations are constant time, and since the iteration is done once per element in the list, the time complexity is O(n)
, where n
is the length of the regular
list (and express
list, as they are of the same length).
Space Complexity
The space complexity of the code is primarily dependent on the cost
list that is being created to store the result at each step. Since this list is the same length as the input lists (regular
and express
), the space required by the cost
list is O(n)
.
The rest of the variables (f
, g
, a
, b
, ff
, gg
, and i
) use a constant amount of space, so they do not add to the complexity in terms of n
. The constants inf
(representing infinity) and expressCost
are also not dependent on n
, so the overall space complexity remains linear with respect to the length of the inputs.
In summary, the space complexity is also O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.
Which of the following method should we use to solve this problem?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!