2361. Minimum Costs Using the Train Line

HardArrayDynamic Programming
Leetcode Link

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, where a 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, where b 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

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 calculate ff and gg which are the tentative costs for the next stop on the regular and express routes respectively.

    • ff is calculated as min(f + a, g + a). Here, f + a is the cost if we continue on the regular route, and g + 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 as min(f + expressCost + b, g + b). The f + expressCost + b part computes the cost if we switch to the express route from the regular route, which includes the expressCost, and g + b computes the cost if we keep going on the express route.

  • After calculating ff and gg, the variables f and g are updated with the new values ff and gg 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 and g at stop i (which has become our new stop i - 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which algorithm should you use to find a node that is close to the root of the tree?

Example 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 is min(f, g) = 1.

  • 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 is min(f, g) = 4.

  • 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 is min(f, g) = 6.

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
Not Sure What to Study? Take the 2-min Quiz

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm should you use to find a node that is close to the root of the tree?

Recommended Readings

Dynamic Programming Introduction and Patterns

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 - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA đŸ‘šâ€đŸ«