983. Minimum Cost For Tickets
Asked at Adobe
Difficulty
Medium
Time
O(365)
Space
O(365)
Pattern
Array
Companies
1
Problem
You know in advance which days of the year you will take the train. Those days are given as days, a sorted list of day numbers (1 to 365). You must buy tickets so that every listed day is covered.
There are three ticket types: a 1-day pass costs costs[0], a 7-day pass costs costs[1], and a 30-day pass costs costs[2]. A pass bought on some day covers that day plus the next 6 or 29 days, depending on its length. You may buy passes on any day, including days you do not travel.
Return the minimum total cost needed to cover all your travel days. You do not need to cover days you are not traveling, and a pass may cover days outside your list for free.
Cover every travel day cheaply
Constraints
- ●
1 <= days.length <= 365 - ●
1 <= days[i] <= 365 - ●
days is in strictly increasing order - ●
costs.length == 3 - ●
1 <= costs[i] <= 1000
Examples
days = [1,4,6,7,8,20], costs = [2,7,15]11days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]17Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Adobe | Medium | View all Adobe questions → |
How to Think About It
Brute force: for each day, recursively try all three pass options and take the minimum.
Use a DP array of size 366 (max days in a year) where dp[i] is the minimum cost to cover days up to day i.
If day i is not a travel day, dp[i] = dp[i-1] (no new cost needed).
If day i is a travel day, dp[i] = min(dp[i-1] + cost1, dp[max(0,i-7)] + cost7, dp[max(0,i-30)] + cost30).
Convert the days list to a set for O(1) lookup. Time O(366), space O(366).
Optimal Approach
Create a boolean set of travel days. Initialize a dp array of size 366 where dp[0] = 0. For each day i from 1 to 365: if not a travel day, dp[i] = dp[i-1]. If it is a travel day, dp[i] = min(dp[i-1] + costs[0], dp[max(0, i-7)] + costs[1], dp[max(0, i-30)] + costs[2]). Return dp[365]. This runs in O(366) time and O(366) space. The key insight is that a pass bought on day i-7 covers day i, so we look back by the pass duration.
DP over the calendar
What Trips People Up in Real Interviews
Clarify the range of days (1 to 365).
Ask whether tickets can overlap (yes, and overlapping is allowed for minimum cost).
Mention that a set for travel days avoids repeated linear searches.
Edge cases: travel on day 1 only, all 365 days are travel days, gaps between travel days.
The dp transition considers max(0, i-duration) to handle boundary conditions cleanly.
Solution Code
O(365) timedef mincostTickets(days, costs):
travel = set(days)
dp = [0] * 366
for i in range(1, 366):
if i not in travel:
dp[i] = dp[i - 1]
else:
dp[i] = min(
dp[i - 1] + costs[0],
dp[max(0, i - 7)] + costs[1],
dp[max(0, i - 30)] + costs[2]
)
return dp[365]Frequently Asked Questions
What is the Minimum Cost For Tickets problem?
Given a list of days you will travel and the costs of 1-day, 7-day, and 30-day tickets, return the minimum cost to cover all travel days. This problem uses dynamic programming where each day's cost is the minimum of buying a 1-day pass, a 7-day pass covering the last 7 days, or a 30-day pass covering the last 30 days.
How do you solve Minimum Cost For Tickets?
The optimal approach runs in O(365) time and O(365) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Minimum Cost For Tickets?
Minimum Cost For Tickets is asked at Adobe. It is a medium difficulty problem.
What are common mistakes on Minimum Cost For Tickets?
- Clarify the range of days (1 to 365).
- Ask whether tickets can overlap (yes, and overlapping is allowed for minimum cost).
- Mention that a set for travel days avoids repeated linear searches.
- Edge cases: travel on day 1 only, all 365 days are travel days, gaps between travel days.
- The dp transition considers max(0, i-duration) to handle boundary conditions cleanly.