Minimum Cost For Tickets — Solution in Python, Java & C++
Minimum Cost For Tickets solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Minimum Cost For Tickets is a medium coding problem on arrays and dynamic programming, asked in Amazon, Google and Uber interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon, Google, Uber
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You have planned train travel for a year, given as a sorted array days of the days you will travel, each between 1 and 365.
Tickets come in three kinds, priced by costs = [oneDay, sevenDay, thirtyDay]: a 1-day pass, a 7-day pass and a 30-day pass, each valid for that many consecutive days starting from the day you buy it.
Return the minimum money needed to cover every travel day.
Example 1
Input: days = [1,4,6,7,8,20], costs = [2,7,15]
Output: 11
Explanation: A 1-day pass on day 1, a 7-day pass on day 3, and a 1-day pass on day 20.
Example 2
Input: days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
Output: 17
Example 3
Input: days = [1], costs = [5,10,20]
Output: 5
Constraints
1 <= days.length <= 501 <= days[i] <= 365days is strictly increasing.1 <= costs[i] <= 1000
Hints for Minimum Cost For Tickets
Hint 1
Work day by day up to the last travel day rather than pass by pass.
Hint 2
On a non-travel day the cost is unchanged from the day before.
Hint 3
On a travel day, try all three passes:
dp[d-1] + cost1,dp[d-7] + cost7,dp[d-30] + cost30, clamping the index at 0.
How to solve Minimum Cost For Tickets
Work day by day to the last travel day; a non-travel day costs nothing extra, a travel day takes the cheapest of a 1-, 7- or 30-day pass bought to cover it.
Approach
- Mark travel days in a boolean array up to
days[-1]. - For each day
d: if not a travel day,dp[d] = dp[d-1]; elsedp[d] = min(dp[d-1] + c1, dp[max(0,d-7)] + c7, dp[max(0,d-30)] + c30). - Return
dp[last].
Why it works
A pass covering day d can be assumed to end on d without loss, so the cost to cover through d is the cost to cover through the day before the pass started plus the pass price.
Complexity
- Time —
O(365) - Space —
O(365)
Pitfalls
- Clamp the index at 0 for passes that would start before day 1.
Reference solution
Python
def mincostTickets(days, costs) -> int:
last = days[-1]
travel = [False] * (last + 1)
for d in days:
travel[d] = True
dp = [0] * (last + 1)
for d in range(1, last + 1):
if not travel[d]:
dp[d] = dp[d - 1]
else:
dp[d] = min(dp[d - 1] + costs[0],
dp[max(0, d - 7)] + costs[1],
dp[max(0, d - 30)] + costs[2])
return dp[last]Java
public static int mincostTickets(int[] days, int[] costs) {
int last = days[days.length - 1];
boolean[] travel = new boolean[last + 1];
for (int d : days) travel[d] = true;
int[] dp = new int[last + 1];
for (int d = 1; d <= last; d++) {
if (!travel[d]) {
dp[d] = dp[d - 1];
} else {
int one = dp[d - 1] + costs[0];
int seven = dp[Math.max(0, d - 7)] + costs[1];
int thirty = dp[Math.max(0, d - 30)] + costs[2];
dp[d] = Math.min(one, Math.min(seven, thirty));
}
}
return dp[last];
}C++
int mincostTickets(vector<int>& days, vector<int>& costs) {
int last = days.back();
vector<char> travel(last + 1, 0);
for (int d : days) travel[d] = 1;
vector<int> dp(last + 1, 0);
for (int d = 1; d <= last; d++) {
if (!travel[d]) {
dp[d] = dp[d - 1];
} else {
int one = dp[d - 1] + costs[0];
int seven = dp[max(0, d - 7)] + costs[1];
int thirty = dp[max(0, d - 30)] + costs[2];
dp[d] = min(one, min(seven, thirty));
}
}
return dp[last];
}JavaScript
var mincostTickets = function(days, costs) {
const last = days[days.length - 1];
const travel = new Array(last + 1).fill(false);
for (let i = 0; i < days.length; i++) travel[days[i]] = true;
const dp = new Array(last + 1).fill(0);
for (let d = 1; d <= last; d++) {
if (!travel[d]) {
dp[d] = dp[d - 1];
continue;
}
const one = dp[d - 1] + costs[0];
const seven = dp[Math.max(0, d - 7)] + costs[1];
const thirty = dp[Math.max(0, d - 30)] + costs[2];
dp[d] = Math.min(one, Math.min(seven, thirty));
}
return dp[last];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming