We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Costs Using the Train Line

Number: 2500

Difficulty: Hard

Paid? Yes

Companies: Citadel

Problem Description

Given two 1-indexed integer arrays regular and express of length n and an integer expressCost, we need to compute a 1-indexed array costs of length n where costs[i] represents the minimum cost to reach stop i from stop 0 (there are n + 1 stops labeled from 0 to n). Movement from stop i-1 to i incurs a cost from either the regular or express route, and switching from the regular route to the express route adds an extra expressCost (with no extra cost to switch back to regular). You start at stop 0 on the regular route.

Key Insights

  • Use dynamic programming to maintain the minimal cost to reach each stop while being on either route.
  • Maintain two state variables (or arrays) for the cost when arriving on the regular route and the express route.
  • At each step, update:
    • The cost on the regular route can come from either staying on regular or switching from the express route (no extra cost to switch back).
    • The cost on the express route can be achieved by either continuing on the express route or by transferring in from the regular route (incurring expressCost).
  • Use an iterative approach to compute the minimal cost for all stops.

Space and Time Complexity

Time Complexity: O(n) – we iterate through each of the n stops once.
Space Complexity: O(1) – we only store constant state (two variables for the current cost) aside from the output array.

Solution

We solve the problem using a dynamic programming approach. We use two state variables: one for the minimum cost to reach the current stop when arriving via the regular route (costRegular) and another for reaching via the express route (costExpress). For each stop i (1-indexed), we update these values as follows:

  • The new cost for the regular route is the minimum cost from the previous stop plus the regular cost for the current segment. It can be reached from either the previous stop on the regular route or the express route (no transfer fee when switching back).
  • The new cost for the express route is the minimum between continuing on the express route (no extra transfer fee) or transferring from the regular route, which adds the expressCost.
    We then take the minimum of the two for each stop to record the answer. This process is repeated for all stops.

Code Solutions

# Python solution with line-by-line comments
def min_costs(regular, express, expressCost):
    n = len(regular)  # Both arrays have length n; stops from 0 to n
    # Initialize dp values: at stop 0, cost for regular is 0 and express is set high (infinity)
    cost_regular = 0
    cost_express = float('inf')
    result = []
    # Iterate through each stop from 1 to n (1-indexed arrays, but our list indices are 0-indexed)
    for i in range(n):
        # Compute new cost for reaching stop i+1 via the regular route
        new_cost_regular = min(cost_regular + regular[i], cost_express + regular[i])
        # Compute new cost for reaching stop i+1 via the express route
        new_cost_express = min(cost_express + express[i], cost_regular + expressCost + express[i])
        # The minimal cost to reach stop i+1 is the minimum of both routes
        min_cost = min(new_cost_regular, new_cost_express)
        # Append the result for stop i+1 (1-indexed output array)
        result.append(min_cost)
        # Update state for the next iteration
        cost_regular, cost_express = new_cost_regular, new_cost_express
    return result

# Example usage:
# regular = [1, 6, 9, 5]
# express = [5, 2, 3, 10]
# expressCost = 8
# Expected output: [1, 7, 14, 19]
print(min_costs([1, 6, 9, 5], [5, 2, 3, 10], 8))
← Back to All Questions