Coding · Dynamic programming
Minimum Cost For Tickets
- Reported in several places
- Medium
- campus SDE (2020)
- 2 sources
Two or more independent public pages, at least one a candidate write-up.
Solve it in the playground, with tests
You plan to travel on certain days of a year, given as a sorted list of day numbers from 1 to 365. A 1-day pass, a 7-day pass and a 30-day pass cost costs[0], costs[1] and costs[2], and a pass covers that many consecutive days starting on the day you buy it. Return the lowest total cost that covers every travel day. For days [1,4,6,7,8,20] and costs [2,7,15] the answer is 11.
Restated in our own words, not a quote from Groww or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would ask: are the days sorted and unique? Do the passes start on the day I buy them, and can I buy one on a day I do not travel? Is a 7-day pass always priced at most seven times a 1-day pass, or can prices be unusual, for example a 30-day pass cheaper than a 7-day one? Do I need the total only, or also which passes to buy? What do I return for no travel days? Is the year fixed at 365 days?
I would assume sorted unique days in 1 to 365, costs for 1, 7 and 30 days in that order, any prices, and a total as the answer, with 0 for no travel.
Brute force
Say the obvious answer and why it is too slow.
Recursion: from the first uncovered travel day, try each of the three passes, jump to the first travel day it does not cover, and recurse. The answer is the cheapest of the three branches. Each call branches three ways and the depth can reach the number of travel days, so it takes O(3^k) time for k travel days. With 365 travel days that is astronomically large.
It is slow because the same tail of the calendar is solved again and again from different paths. For example, buying seven 1-day passes and buying one 7-day pass both lead to the same remaining days, and each time the whole subtree is recomputed.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(3^k) for k travel days
- Time
- O(D), D at most 365
- Space
- O(D)
The pattern is one-dimensional dynamic programming over the calendar. Let cheapest[d] be the lowest cost to cover all travel days up to and including day d. Build it from day 1 up to the last travel day.
If day d is not a travel day, nothing new must be covered, so cheapest[d] equals cheapest[d - 1]. If it is a travel day, think of d as the last day to cover. Some pass must cover it, and that pass can be slid so that it ends on d, since days after d do not matter. A 1-day pass covers just d, so the rest costs cheapest[d - 1]. A 7-day pass ending on d covers d - 6 to d, so the rest costs cheapest[d - 7]. A 30-day pass covers d - 29 to d, so the rest costs cheapest[d - 30]. Take the cheapest of the three sums; when d - 7 or d - 30 drops below 0, use cheapest[0] = 0.
Why this is correct: the cheapest cover of the days up to d must use one of these three passes on d, and what remains is the same problem for earlier days, whose best answer is already stored. Using the stored value is safe because the cost of the earlier days does not depend on how the later part is paid for.
The table has at most 366 entries and each takes three comparisons, so the work is tiny. The lookup of whether a day is a travel day uses a Set, which is O(1) on average. I would say it as: the cost up to day d is the best of the three passes that could end today.
Walk it through
A dry run on the example, step by step.
| Day | 1-day option | 7-day option | 30-day option | cheapest[day] |
|---|---|---|---|---|
| 1 | 0 + 2 = 2 | 0 + 7 = 7 | 0 + 15 = 15 | 2 |
| 4 | 2 + 2 = 4 | 0 + 7 = 7 | 0 + 15 = 15 | 4 |
| 6 | 4 + 2 = 6 | 0 + 7 = 7 | 0 + 15 = 15 | 6 |
| 7 | 6 + 2 = 8 | 0 + 7 = 7 | 0 + 15 = 15 | 7 |
| 8 | 7 + 2 = 9 | 2 + 7 = 9 | 0 + 15 = 15 | 9 |
| 20 | 9 + 2 = 11 | 9 + 7 = 16 | 0 + 15 = 15 | 11 |
Use days [1,4,6,7,8,20] and costs [2,7,15]. Non-travel days copy the previous value, so the trace lists only travel days. Day 1: a 1-day pass gives cheapest[0] + 2 = 2, so the cost is 2. Day 4: cheapest[3] is still 2, so a 1-day pass gives 4; a 7-day pass gives 0 + 7 = 7; the best is 4. Day 6: cheapest[5] is 4, giving 6, which beats 7.
Day 7: a 1-day pass gives 6 + 2 = 8, but a 7-day pass reaching back to day 1 gives cheapest[0] + 7 = 7, so the best drops to 7. Day 8: a 1-day pass gives 9 and a 7-day pass gives cheapest[1] + 7 = 9; the best is 9. Day 20: days 9 to 19 are free, so cheapest[19] = 9, and a 1-day pass gives 11, beating 16 and 15. The answer is 11.
The code
Runnable JavaScript, checked against test cases.
function minCostTickets(days, costs) {
const durations = [1, 7, 30];
const travelDays = new Set(days);
const lastDay = days.length === 0 ? 0 : days[days.length - 1];
const cheapest = new Array(lastDay + 1).fill(0);
for (let day = 1; day <= lastDay; day++) {
if (!travelDays.has(day)) {
cheapest[day] = cheapest[day - 1];
continue;
}
let best = Infinity;
for (let t = 0; t < durations.length; t++) {
const before = Math.max(0, day - durations[t]);
best = Math.min(best, cheapest[before] + costs[t]);
}
cheapest[day] = best;
}
return cheapest[lastDay];
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
No travel days: the last day is 0, the table has one cell holding 0, and the answer is 0. One travel day: the cheapest single option, which could even be a 7-day pass if that is priced below a 1-day one. A pass reaching back before day 1: Math.max(0, ...) clamps the index, so the code reads cheapest[0] = 0 instead of a negative index.
Unusual prices: a 7-day pass cheaper than a 1-day pass is handled because all three options are always compared. Travel on day 365: the table holds 366 cells, which is fine. Non-travel days copy the previous value so that a 30-day option can look back across a gap and still read a valid number. The input arrays are read, never modified.
Follow-ups to expect
Where the interviewer pushes next.
- How would you also return which passes to buy and on which days?
- How would you solve it if the day numbers could be as large as a billion?
- How could you use the days array directly with a pointer and avoid the calendar table?
- What changes if passes of arbitrary lengths are given in an array?
- Why does a simple greedy rule fail on this problem?
Where candidates slip
The mistakes this problem punishes.
A common slip is indexing the table by position in the days array while using day arithmetic such as day - 7, which mixes two kinds of index. Pick one: calendar days, as here, or array positions with a pointer. Another is forgetting the clamp, which gives a negative index, an undefined cost and then NaN.
Others: a greedy rule such as buy the 7-day pass whenever the next seven days hold enough trips, which breaks on unusual prices; forgetting that on a travel day all three options must be compared, not only the 1-day pass; sizing the table to 365 regardless of the input, which is harmless but hides the real dependence on the last day; and writing the recursion without caching, which is correct on small tests and far too slow on a year of travel.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.