Minimum Cost For Tickets
Asked at Adobe
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.
Asked At
| 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.
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
def 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.