You are given:
- an array
days[]representing the days you will travel - three ticket types with durations and costs:
- 1-day pass:
costs[0] - 7-day pass:
costs[1] - 30-day pass:
costs[2]
- 1-day pass:
Your task:
Return the minimum total cost required to cover all travel days.
Example:
Input: days = [1,4,6,7,8,20] costs = [2,7,15] Output: 11 Explanation: Buy 1-day pass on day 1 → cost 2 Buy 7-day pass on day 6 covers days 6–12 → cost 7 Total = 9 but still must cover day 20 → best option is: Buy 1-day pass on day 20 → cost 2 Final total = 2 + 7 + 2 = 11
Problem Understanding
Key observations:
- You do not travel every day — only days listed in array
- Purchasing a pass covers a continuous range of days
- You want a combination of passes that covers all travel days at minimum cost
- Greedy choices don’t always work because:
- A 30-day pass may be cheaper than several 7-day passes
- Local cheapest choice may not lead to global minimum
Therefore, dynamic programming is needed.
Logic Explained in Simple English
The simplest way to think about this:
- You move through the calendar day by day.
- On each travel day, you decide:
- Should I buy a 1-day pass?
- Or a 7-day pass?
- Or a 30-day pass?
- Each choice affects future coverage.
- You pick the option that leads to the cheapest overall cost.
Better thought:
- If today is not a travel day → cost remains same as yesterday
- If today is a travel day:
- Option 1: cost if buying 1-day pass today
- Option 2: cost if buying 7-day pass today (look back 7 days)
- Option 3: cost if buying 30-day pass today (look back 30 days)
So we compute:
dp[day] = minimum cost to cover all travel up to this day
Final answer is dp[last travel day].
Why this works:
- We explore all valid ticket decisions
- We reuse previously computed optimal results
- We only compute up to the max travel day (at most 365)
Step-by-Step Approach
- Convert travel days into a set for fast lookup
- Find the last day you travel
- Create dp array of size lastDay+1
- For each day from 1 to lastDay:
- If day not in travel days: dp[day] = dp[day-1]
- Else:
- cost1 = dp[day-1] + costs[0]
- cost7 = dp[max(0, day-7)] + costs[1]
- cost30 = dp[max(0, day-30)] + costs[2]
- dp[day] = min(cost1, cost7, cost30)
- Return dp[lastDay]
Java Implementation
class Solution {
public int mincostTickets(int[] days, int[] costs) {
Set<Integer> travelDays = new HashSet<>();
int lastDay = days[days.length - 1];
for (int d : days) {
travelDays.add(d);
}
int[] dp = new int[lastDay + 1];
for (int day = 1; day <= lastDay; day++) {
if (!travelDays.contains(day)) {
dp[day] = dp[day - 1];
} else {
int cost1 = dp[Math.max(0, day - 1)] + costs[0];
int cost7 = dp[Math.max(0, day - 7)] + costs[1];
int cost30 = dp[Math.max(0, day - 30)] + costs[2];
dp[day] = Math.min(cost1, Math.min(cost7, cost30));
}
}
return dp[lastDay];
}
}
Dry Run Example
Input:
days = [1,4,6,7,8,20] costs = [2,7,15]
lastDay = 20
We track only days in set:
{1,4,6,7,8,20}
Build dp:
Day 1:
travel day dp[1] = min( dp[0] + 2, dp[0] + 7, dp[0] + 15 ) = 2
Day 2,3:
no travel → dp stays 2
Day 4:
dp[4] = min( dp[3] + 2 = 4, dp[0] + 7 = 7, dp[0] + 15 = 15 ) = 4
Day 6:
dp[6] = min( dp[5] + 2 = 6, dp[0] + 7 = 7, dp[0] + 15 = 15 ) = 6
Day 7:
dp[7] = min( dp[6] + 2 = 8, dp[0] + 7 = 7, dp[0] + 15 = 15 ) = 7
Day 8:
dp[8] = min( dp[7] + 2 = 9, dp[1] + 7 = 9, dp[0] + 15 = 15 ) = 9
Day 20:
dp[20] = min( dp[19] + 2 = 11, dp[13] + 7 = 14, dp[0] + 15 = 15 ) = 11
Final answer:
11
Time and Space Complexity
Time Complexity
O(lastDay)
Worst case lastDay = 365 → fast.
Space Complexity
O(lastDay)
Common Mistakes and How to Avoid Them
Mistake 1: Trying greedy
Cheapest today does not ensure cheapest total.
Mistake 2: Only considering next travel day
Pass coverage spans non-travel days too.
Mistake 3: Using dp sized by number of travel days
Incorrect because coverage windows rely on real day indexes.
Mistake 4: Forgetting dp boundary when subtracting days
Use:
dp[Math.max(0, day - 7)]
Mistake 5: Miscounting which days are covered
Pass duration counts inclusive, meaning:
- 7-day pass covers day to day+6