Minimum Costs Using the Train Line - Solution & Explanation

Q: Is Minimum Costs Using the Train Line easy or hard?

Minimum Costs Using the Train Line is labeled Hard because it requires modeling two DP states and handling a one-time transition cost correctly. Once the state transitions are defined, the implementation becomes a linear-time dynamic programming solution.

Q: Minimum Costs Using the Train Line Python/Java solution

The solution in Python, Java, C++, Go, or TypeScript follows the same idea: maintain two DP states for regular and express travel. Update them while iterating through the arrays and append the minimum of the two states for each station.

Q: How to solve Minimum Costs Using the Train Line in O(n)?

Track two running costs: the minimum cost to reach the current station using the regular line and using the express line. For every station, update these values based on staying on the same line or switching to express with the additional entry cost. Iterating through the arrays once produces the minimum cost for each station.

Q: What is the best approach for Minimum Costs Using the Train Line?

The best approach uses dynamic programming with two states: cost reaching a station via the regular line and via the express line. By updating these states for each station, you compute the minimum cost efficiently in O(n) time. The optimized version stores only the previous state, reducing space to O(1).

Q: Is Minimum Costs Using the Train Line asked at Google/Amazon/Meta?

Dynamic programming problems with multiple states and transition costs appear frequently in interviews at companies like Google, Amazon, and Meta. Variations of this problem test state modeling, cost transitions, and space optimization techniques.

Q: What data structure is used in Minimum Costs Using the Train Line?

The core structure is dynamic programming over arrays. Two variables or a DP table track the minimum cost for regular and express lines at each station while iterating through the cost arrays.

Q: What is the time complexity of Minimum Costs Using the Train Line?

The optimal solution runs in O(n) time because each station is processed once while updating two DP states. Space complexity can be O(n) with a full DP table or O(1) with a rolling-state optimization.

HardPremiumFree on FleetCodeArray Dynamic Programming12 min readAsked at: Citadel

Practice this problem

Problem Statement

A train line going through a city has two routes, the regular route and the express route. Both routes go through the same n + 1 stops labeled from 0 to n. Initially, you start on the regular route at stop 0.

You are given two 1-indexed integer arrays regular and express, both of length n. regular[i] describes the cost it takes to go from stop i - 1 to stop i using the regular route, and express[i] describes the cost it takes to go from stop i - 1 to stop i using the express route.

You are also given an integer expressCost which represents the cost to transfer from the regular route to the express route.

Note that:

There is no cost to transfer from the express route back to the regular route.
You pay expressCost every time you transfer from the regular route to the express route.
There is no extra cost to stay on the express route.

Return a 1-indexed array costs of length n, where costs[i] is the minimum cost to reach stop i from stop 0.

Note that a stop can be counted as reached from either route.

Example 1:

Input: regular = [1,6,9,5], express = [5,2,3,10], expressCost = 8
Output: [1,7,14,19]
Explanation: The diagram above shows how to reach stop 4 from stop 0 with minimum cost.
- Take the regular route from stop 0 to stop 1, costing 1.
- Take the express route from stop 1 to stop 2, costing 8 + 2 = 10.
- Take the express route from stop 2 to stop 3, costing 3.
- Take the regular route from stop 3 to stop 4, costing 5.
The total cost is 1 + 10 + 3 + 5 = 19.
Note that a different route could be taken to reach the other stops with minimum cost.

Example 2:

Input: regular = [11,5,13], express = [7,10,6], expressCost = 3
Output: [10,15,24]
Explanation: The diagram above shows how to reach stop 3 from stop 0 with minimum cost.
- Take the express route from stop 0 to stop 1, costing 3 + 7 = 10.
- Take the regular route from stop 1 to stop 2, costing 5.
- Take the express route from stop 2 to stop 3, costing 3 + 6 = 9.
The total cost is 10 + 5 + 9 = 24.
Note that the expressCost is paid again to transfer back to the express route.

Constraints:

n == regular.length == express.length
1 <= n <= 10⁵
1 <= regular[i], express[i], expressCost <= 10⁵

Approach Overview

Problem Overview: You travel through n train stations. At each station you can continue on the regular line or switch to an express line that requires a one-time expressCost. Each segment has different travel costs for the regular and express lines. The task is to compute the minimum cost to reach every station.

The key difficulty is modeling the state when switching lines. Once you pay the express entry cost, you can keep using the express line for later segments without paying it again.

Approach 1: Full Dynamic Programming with State Table (O(n) time, O(n) space)

Use dynamic programming with two states per station: the minimum cost if you arrive using the regular line and the minimum cost if you arrive using the express line. Let dp[i][0] represent reaching station i on the regular line and dp[i][1] represent reaching it on the express line.

For each station, compute transitions from the previous station. Staying on the regular line adds regular[i]. Moving to the express line either continues from express or switches from regular and adds expressCost. Iterate through the array of costs and update both states. The minimum cost to reach station i is min(dp[i][0], dp[i][1]). This approach is straightforward and clearly shows the two-line state transition.

Approach 2: Space-Optimized Dynamic Programming (O(n) time, O(1) space)

The transition only depends on the previous station, so storing the entire DP table is unnecessary. Maintain two variables: regularCost (minimum cost reaching the current station via the regular line) and expressCostState (minimum cost reaching it via the express line).

At each step, compute the new costs using the previous values. Continuing regular adds regular[i]. Continuing express adds express[i]. Switching from regular to express requires paying the one-time expressCost plus the segment cost. Update both states and record min(regularCost, expressCostState) for the answer.

This rolling-state technique removes the O(n) memory while preserving the same transition logic. The algorithm processes the cost arrays once, making it optimal for large inputs.

Recommended for interviews: The space-optimized dynamic programming approach. Interviewers expect you to identify the two-state DP (regular vs express) and then compress the state to constant memory. Writing the full DP table first shows clear reasoning; optimizing to O(1) space demonstrates stronger problem-solving skills.

Solution

We define f[i] as the minimum cost from station 0 to station i when arriving at station i by the regular route, and g[i] as the minimum cost from station 0 to station i when arriving at station i by the express route. Initially, f[0]=0, g[0]=infty.

Next, we consider how to transition the states of f[i] and g[i].

If we arrive at station i by the regular route, we can either come from station i-1 by the regular route or switch from the express route at station i-1 to the regular route. Therefore, we can get the state transition equation:

$f[i]=min{f[i-1]+a_i, g[i-1]+a_i}

where a_i represents the cost of taking the regular route from station i-1 to station i.

If we arrive at station i by the express route, we can either switch from the regular route at station i-1 to the express route or continue on the express route from station i-1. Therefore, we can get the state transition equation:

g[i]=min{f[i-1]+expressCost+b_i, g[i-1]+b_i}

where b_i represents the cost of taking the express route from station i-1 to station i.

We denote the answer array as cost, where cost[i] represents the minimum cost from station 0 to station i. Since we can reach station i from any route, we have cost[i]=min{f[i], g[i]}.

Finally, we return cost.

The time complexity is O(n) and the space complexity is O(n), where n$ is the number of stations.

Code

Python Java C++Go TypeScript

Python

Java

C++

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Dynamic Programming (2D State Table)	O(n)	O(n)	Best for understanding transitions between regular and express lines
Space-Optimized Dynamic Programming	O(n)	O(1)	Preferred in interviews and production when memory usage matters

Video Solution

Leetcode 2361. Minimum Costs Using the Train Line: DP • Code-Yao • 1,143 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Minimum Costs Using the Train Line easy or hard?

Minimum Costs Using the Train Line is labeled Hard because it requires modeling two DP states and handling a one-time transition cost correctly. Once the state transitions are defined, the implementation becomes a linear-time dynamic programming solution.

Minimum Costs Using the Train Line Python/Java solution

The solution in Python, Java, C++, Go, or TypeScript follows the same idea: maintain two DP states for regular and express travel. Update them while iterating through the arrays and append the minimum of the two states for each station.

How to solve Minimum Costs Using the Train Line in O(n)?

Track two running costs: the minimum cost to reach the current station using the regular line and using the express line. For every station, update these values based on staying on the same line or switching to express with the additional entry cost. Iterating through the arrays once produces the minimum cost for each station.

What is the best approach for Minimum Costs Using the Train Line?

The best approach uses dynamic programming with two states: cost reaching a station via the regular line and via the express line. By updating these states for each station, you compute the minimum cost efficiently in O(n) time. The optimized version stores only the previous state, reducing space to O(1).

Is Minimum Costs Using the Train Line asked at Google/Amazon/Meta?

Dynamic programming problems with multiple states and transition costs appear frequently in interviews at companies like Google, Amazon, and Meta. Variations of this problem test state modeling, cost transitions, and space optimization techniques.

What data structure is used in Minimum Costs Using the Train Line?

The core structure is dynamic programming over arrays. Two variables or a DP table track the minimum cost for regular and express lines at each station while iterating through the cost arrays.

What is the time complexity of Minimum Costs Using the Train Line?

The optimal solution runs in O(n) time because each station is processed once while updating two DP states. Space complexity can be O(n) with a full DP table or O(1) with a rolling-state optimization.

Ready to solve this problem?

Practice Minimum Costs Using the Train Line with our built-in code editor and test cases.

Practice on FleetCode

Bus Routes

Distance Between Bus Stops

Problem Info

DifficultyHard

Acceptance77.7%

Approaches1

Reading time12 min

Asked at

Citadel