Minimum Cost For Tickets

Minimum Cost For Tickets

What is this problem about?

The Minimum Cost For Tickets problem asks you to find the cheapest way to travel on specific days of the year. You can buy three types of tickets:

1. A 1-day pass.
2. A 7-day pass.
3. A 30-day pass. Each pass has a different cost. You are given a sorted list of days you need to travel. The goal is to cover all those days with the minimum total ticket cost.

Why is this asked in interviews?

This is an extremely popular Minimum Cost For Tickets interview question at companies like Amazon, Google, and Microsoft. It is a textbook example of Dynamic Programming. It tests your ability to define a state and a recurrence relation where the current choice (which ticket to buy) depends on the optimal cost of covering future or past days.

Algorithmic pattern used

The Dynamic Programming interview pattern (either top-down with memoization or bottom-up) is the standard solution.

1. dp[i] represents the minimum cost to cover all travel days from day i to the end of the year.
2. If day i is not a travel day, dp[i] = dp[i+1].
3. If day i IS a travel day, you have three choices:
   • Buy 1-day pass: cost[0] + dp[i+1]
   • Buy 7-day pass: cost[1] + dp[i+7]
   • Buy 30-day pass: cost[2] + dp[i+30]
4. Take the minimum of these three options.

Example explanation

Days: [1, 4, 6, 7, 8, 20], Costs: [2, 7, 15].

1. On day 20, a 1-day pass is cheapest (2).
2. On day 1, you could buy a 1-day pass, but buying a 7-day pass covers days 1, 4, 6, and 7.
3. The DP table will compare the cost of 2+2+2+2 (four 1-day passes = 8) against 7 (one 7-day pass).
4. The algorithm systematically finds the optimal combination for the entire schedule.

Common mistakes candidates make

• Greedy approach: Always buying the 7-day or 30-day pass if it "looks" cheaper. This fails on schedules with large gaps.
• Inefficient lookups: Not using a boolean array or a set to quickly check if a day is a travel day.
• Incorrect indexing: Forgetting that a 7-day pass bought on day 1 lasts until day 7 (inclusive), so the next day to consider is day 8.

Interview preparation tip

Practice both the Top-Down and Bottom-Up versions of this Dynamic Programming coding problem. Interviewers often ask to optimize the space complexity. Since a pass only lasts 30 days, you can actually solve this using only $O(30)$ space with a deque.