Problem Explanation

The problem is asking for us to find the most cost-effective way to travel by train within a year given a list of days we plan to travel on and three types of ticket passes that are available: a single day pass, a 7 day pass, and a 30 day pass. Each pass type has a different cost associated with it.

For example, in the first example, we are given the following days we want to travel: 1, 4, 6, 7, 8, 20 and costs for each pass type of [2, 7, 15]. The task is to figure out which pass to buy on each day so we spend the least amount of money for the year. In this case, it would be best to buy a 1-day pass on day 1, a 7-day pass on day 4, and another 1-day pass on day 20. This way we cover all planned days and only spend a total of $11.

Solution Approach

The solution involves using a dynamic programming approach. We create two queues, one for the last 7 days and one for the last 30 days. These queues are used to keep track of the minimum cost to travel up to that day.

Then we iterate through each day in our travel plan. If a day in the queue has already been covered by a pass, we pop it from the queue. Then we add the current day to each queue, indicating that we purchase a 7-day pass and a 30-day pass.

At each day, we update the minimum cost to travel up to that day. It can be the minimum of three options: the cost of the previous day plus a 1-day pass, the cost of 7 days ago plus a 7-day pass, or the cost of 30 days ago plus a 30-day pass.

Finally, we return the minimum cost to travel all planed days.

Python Solution

1
2python
3from collections import deque
4class Solution:
5    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
6        last7, last30 = deque(), deque()
7        ans = 0
8        for day in days:
9            # pop days that are covered by a pass
10            while last7 and last7[0][0]+7 <= day:
11                last7.popleft()
12            while last30 and last30[0][0]+30 <= day:
13                last30.popleft()
14            # add the current day, as if we bought a ticket that day
15            last7.append((day, ans + costs[1]))
16            last30.append((day, ans + costs[2]))
17            # Find the minimum cost to travel so far
18            ans = min(ans + costs[0], last7[0][1], last30[0][1])
19        return ans

Java Solution

1
2java
3class Solution {
4    public int mincostTickets(int[] days, int[] costs) {
5        Queue<int[]> last7 = new LinkedList<>();
6        Queue<int[]> last30 = new LinkedList<>();
7        int ans = 0;
8        for (int day : days) {
9            while (!last7.isEmpty() && last7.peek()[0] + 7 <= day)
10                last7.poll();
11            while (!last30.isEmpty() && last30.peek()[0] + 30 <= day)
12                last30.poll();
13            last7.add(new int[]{day, ans + costs[1]});
14            last30.add(new int[]{day, ans + costs[2]});
15            ans = Math.min(ans + costs[0], Math.min(last7.peek()[1], last30.peek()[1]));
16        }
17        return ans;
18    }
19}

JavaScript Solution

1
2javascript
3var mincostTickets = function (days, costs) {
4    let last7 = [], last30 = [];
5    let ans = 0;
6    for (let day of days) {
7        while (last7.length && last7[0][0] + 7 <= day)
8            last7.shift();
9        while (last30.length && last30[0][0] + 30 <= day)
10            last30.shift();
11        last7.push([day, ans + costs[1]]);
12        last30.push([day, ans + costs[2]]);
13        ans = Math.min(ans + costs[0], last7[0][1], last30[0][1]);
14    }
15    return ans;
16};

C++ Solution

1
2cpp
3class Solution {
4public:
5    int mincostTickets(vector<int>& days, vector<int>& costs) {
6        queue<pair<int, int>> last7, last30;
7        int ans = 0;
8        for (int day : days) {
9            while (!last7.empty() && last7.front().first + 7 <= day)
10                last7.pop();
11            while (!last30.empty() && last30.front().first + 30 <= day)
12                last30.pop();
13            last7.push({ day, ans + costs[1] });
14            last30.push({ day, ans + costs[2] });
15            ans = min({ ans + costs[0], last7.front().second, last30.front().second });
16        }
17        return ans;
18    }
19};

C# Solution

1
2csharp
3public class Solution {
4    public int MincostTickets(int[] days, int[] costs) {
5        Queue<int[]> last7 = new Queue<int[]>();
6        Queue<int[]> last30 = new Queue<int[]>();
7        int ans = 0;
8        foreach (int day in days) {
9            while (last7.Count > 0 && last7.Peek()[0] + 7 <= day)
10                last7.Dequeue();
11            while (last30.Count > 0 && last30.Peek()[0] + 30 <= day)
12                last30.Dequeue();
13            last7.Enqueue(new int[]{day, ans + costs[1]});
14            last30.Enqueue(new int[]{day, ans + costs[2]});
15            ans = Math.Min(ans + costs[0], Math.Min(last7.Peek()[1], last30.Peek()[1]));
16        }
17        return ans;
18    }
19}

In all these solutions, we are using queues (FIFO structure) to keep track of the possible passes we could use on each day. The queues are always kept in increasing order of the cost to reach that day, so that the front of the queue always has the cheapest option.Here, we've used dynamic programming to calculate the cheapest tickets we can buy. We start by initializing two queues: last7 and last30 which store the day and the minimum cost to travel up to that day if we were to use a 7 and 30-day ticket, respectively. Then, for each day in the travel plan, we iterate from the beginning of last7 and last30, discarding any day that's at least 7 or 30 days before the current day as we would not be able to travel on that day with the 7 and 30-day tickets, respectively.

After that, we add the current day to last7 and last30, indicating that we are considering the option of buying a 7 and 30-day ticket on that day. Next, we keep a running total of the minimum cost to travel up to the current day. This cost is the minimum between the cost of the previous day plus a 1-day ticket, and the cost of buying a 7-day ticket or a 30-day ticket 7 or 30 days ago, respectively.

We return the minimum travel cost after considering all travel days. Depending on the specific days we need to travel and the costs of the different tickets, the minimum cost to travel can be achieved by different combinations of 1, 7, and 30-day tickets.

The complexity of this approach is O(n), where n is the number of travel days. This is because we visit every travel day once and each operation within the loop (i.e., adding to the queue, removing from the queue, and calculating the minimum cost) takes constant time. Additionally, the space complexity is also O(n), as in the worst case, we may store up to n days in last7 and last30.

We've now seen how to solve this problem using dynamic programming in Python, Java, JavaScript, C++ and C#. Despite the differences in syntax, the logic of the solution is essentially the same across all these languages.