983. Minimum Cost For Tickets
Problem Description
In this train traveling problem, you are given an integer array days, which represents each day in the year you will travel by train. The days are within the range from 1 to 365. The goal is to find the minimum cost needed to purchase train tickets to cover all those traveling days within a year.
There are three types of train passes you can buy:
- A 1-day pass for
costs[0]dollars. - A 7-day pass for
costs[1]dollars. - A 30-day pass for
costs[2]dollars.
A pass allows you to travel for that number of consecutive days. For instance, if you buy a 7-day pass on day 2, you can travel from day 2 to day 8 inclusively.
You need to determine the minimum total cost to buy passes such that you can travel on all the days listed in the array days.
Intuition
To tackle this problem, we need to consider that buying a longer-term pass (7-day or 30-day) might be cheaper in the long run even if we don't use all of its valid days. Our solution must weigh the costs and benefits of each type of pass for each travel day.
We can think about the problem in terms of decision-making on each traveling day: should we buy a 1-day, 7-day, or 30-day pass? After buying a pass, we'd like to know "when do we have to make the next decision?â This leads to a recursive solution where we try all possible pass purchases and choose the one with the lowest overall cost.
For each day in days we are traveling, we have three choices: buy a 1-day pass, buy a 7-day pass, or buy a 30-day pass. After we buy a pass, we will skip to the next day that is outside the range of the pass. For example, if we're considering buying a 7-day pass on day i, the next decision would be made for the first day after those 7 days.
The mincostTickets function uses dynamic programming to avoid recalculating the minimum cost for days that have already been processed. A dfs function is used to find the minimum cost recursively, starting from the first day in days. The @cache decorator is used to memoize results, which saves the results of subproblems and dramatically reduces the time complexity.*
An array could also be used to cache results, but using the @cache decorator is cleaner and avoids the need to explicitly manage the caching logic.
Using binary search (bisect_left from the bisect module), we determine the day to continue the search from after buying a particular pass. The bisect_left function finds the position to insert an element to keep the list sorted and is used here to find the first travel day that is not covered by the current pass being considered.
The recursion's base case is when i goes beyond the last travel day, returning a cost of 0 because no further tickets need to be purchased.
We iterate through all types of passes, calculate the total cost if we bought a particular type of pass, and then take the minimum of those costs. The result from the dfs function called with 0, the first day, gives us the minimum cost required for all the travel days.
*As of the knowledge cutoff date in September 2021, the @cache decorator is available in Python 3.9 and later as part of the functools module.
Learn more about Dynamic Programming patterns.
Which of these properties could exist for a graph but not a tree?
Solution Approach
The solution takes a dynamic programming approach using recursion with memoization to keep track of the subproblems that have already been solved. Here's a breakdown of the implementation:
-
Recursion: The core algorithm is a recursive function
dfs(i), which computes the minimum cost starting from thei-th travel day in thedaysarray. Ifiis equal to or greater than the length ofdays, it means all travel days have been covered, and the function returns0. -
Memoization: The use of the
@cachedecorator from thefunctoolsmodule automatically stores the results of the recursive calls. This way, when the function is called again with the samei, it returns the stored result instead of recomputing it. This memoization significantly speeds up the execution by eliminating duplicate calculations. -
Binary Search: The
bisect_leftfunction from thebisectmodule efficiently finds the smallest indexjat which the daydays[i] + dcould be inserted to maintain the sorted order. Here,drepresents the duration of the pass (1, 7, or 30 days), and findingjallows us to determine the first day that is not covered by the pass. This helps us move to the next subproblem without iterating over each day. -
Minimum Cost Calculation: The recursive function tries to simulate buying each type of pass (1-day, 7-day, or 30-day), and for each case, it adds the cost of the pass
cto the result of the recursive call for the next uncovered daydfs(j). Then, it stores the minimum of these calculated costs in the variableres.
The dynamics of the function are as follows:
- We iterate over each type of pass using a loop
for c, d in zip(costs, [1, 7, 30]):. - We find the next index
jto call our function recursively viaj = bisect_left(days, days[i] + d). - We calculate the cost of buying the current pass and add it to the cost of all future decisions:
res = min(res, c + dfs(j)). - After trying all pass options for day
i,reswill contain the minimum cost to cover dayiand all subsequent days.
After the setup of the recursive function and decorators, the solution is initiated by calling return dfs(0). The result is the minimum total cost to purchase train tickets for all the traveling days.
This algorithm efficiently decides the best pass to buy for each travel day, considering all the possible options and their costs, to come up with the minimum total cost for all travel days.
Is the following code DFS or BFS?
1void search(Node root) { 2 if (!root) return; 3 visit(root); 4 root.visited = true; 5 for (Node node in root.adjacent) { 6 if (!node.visited) { 7 search(node); 8 } 9 } 10}
Example Walkthrough
Let's illustrate the solution approach with a small example. Assume the days array in which we will travel is given by [1, 4, 6, 7, 8, 20], and the costs of train passes are available as [2, 7, 15] for 1-day, 7-day, and 30-day passes, respectively.
We start by calling the dfs function with i = 0, which corresponds to the first traveling day, day 1.
-
Day 1 Decision:
- Buy a 1-day pass for
costs[0]or$2. Our next decision will be on day4(next travel day after day1). - Buy a 7-day pass for
costs[1]or$7. The next decision day will be day20(as days4,6,7, and8all fall within the 7-day period starting day1). - Buy a 30-day pass for
costs[2]or$15. Since the 30-day pass covers the entiredaysarray in this example, this would mean no more decisions are necessary.
- Buy a 1-day pass for
-
Subsequent Decisions:
- If we bought a 1-day pass for the first day, on day
4, we face similar options (buy a 1-day, 7-day, or 30-day pass), and the same applies for days6,7,8, and20. Each option's cost is calculated and added to the initial$2. - If we chose a 7-day pass, we next buy a pass on day
20. Here, since itâs the last day, we'd only consider a 1-day pass, which adds$2to the initial$7.
- If we bought a 1-day pass for the first day, on day
-
Memoization:
- During the process, all calculated costs are stored, and if a day is reached that has been previously calculated, we simply use the stored value.
-
Recursive Calls and Minimum Cost Calculation:
- The
dfs(4)call calculates the minimum cost from day4and so on. For example, ifdfs(4)returns$9(cheapest way to cover days4, 6, 7, 8, 20), the total cost of buying a 1-day pass on day1and using the optimal strategy onward is$2 + $9 = $11.
- The
-
Final Decision:
- After exploring all options, we take the minimum total cost to purchase train tickets for all travel days. In our case, it's min(
$2+dfs(4),$7+dfs(20),$15).
- After exploring all options, we take the minimum total cost to purchase train tickets for all travel days. In our case, it's min(
Assuming dfs(4) returns $9 (example value), dfs(20) returns $2, the final costs would be $11, $9, and $15, and the minimum cost is thus $9. So buying a 7-day pass on day 1 and a 1-day pass on day 20 would be the optimal solution here.
Solution Implementation
1from bisect import bisect_left
2from functools import lru_cache
3
4class Solution:
5 def mincostTickets(self, days: List[int], costs: List[int]) -> int:
6 # Using lru_cache from functools to memoize results of recursive calls
7 # This will store results of the subproblems so they do not need to be recomputed
8 @lru_cache(maxsize=None)
9 def min_cost_from_day(index):
10 # Base case: when all days have been covered
11 if index >= len(days):
12 return 0
13
14 # Initialize result as infinity to ensure any minimum will be taken
15 result = float('inf')
16
17 # Iterate over each type of ticket to cover future travel
18 for ticket_cost, validity_duration in zip(costs, [1, 7, 30]):
19 # Find the next day index when the current ticket will be expired
20 next_index = bisect_left(days, days[index] + validity_duration)
21 # Calculate the cost if we select current ticket and call recursively for the remaining days
22 total_cost = ticket_cost + min_cost_from_day(next_index)
23 # Update the minimum result
24 result = min(result, total_cost)
25
26 # Return the minimum cost found
27 return result
28
29 # Start from the first day we have in the list
30 return min_cost_from_day(0)
311public class Solution {
2
3 // Define constants for pass durations
4 private static final int[] PASS_DURATIONS = new int[]{1, 7, 30};
5
6 // Variables to store costs, days, and memoized values
7 private int[] passCosts;
8 private int[] travelDays;
9 private int[] memo;
10 private int totalDays;
11
12 // Method to calculate the minimum cost of tickets for given travel days and ticket costs
13 public int mincostTickets(int[] days, int[] costs) {
14 totalDays = days.length;
15 memo = new int[totalDays];
16 this.passCosts = costs;
17 this.travelDays = days;
18
19 // Fill memo array with default values to denote not calculated
20 Arrays.fill(memo, -1);
21
22 // Start DFS from the first day
23 return dfs(0);
24 }
25
26 // Helper method to perform Depth-First Search (DFS)
27 private int dfs(int currentIndex) {
28 // Base case: if the currentIndex is beyond the last day, no cost is needed
29 if (currentIndex >= totalDays) {
30 return 0;
31 }
32
33 // If the cost has already been computed, return it
34 if (memo[currentIndex] != -1) {
35 return memo[currentIndex];
36 }
37
38 // Initialize result as the maximum value
39 int result = Integer.MAX_VALUE;
40
41 // Consider all types of passes
42 for (int k = 0; k < 3; ++k) {
43 // Find the index of the next day right after the pass expires
44 int nextIndex = lowerBound(travelDays, travelDays[currentIndex] + PASS_DURATIONS[k]);
45
46 // Calculate the minimum cost using the chosen pass
47 result = Math.min(result, passCosts[k] + dfs(nextIndex));
48 }
49
50 // Save result to memo array
51 memo[currentIndex] = result;
52
53 // Return the final minimized cost
54 return result;
55 }
56
57 // Helper method to find the lower bound index for a given day (binary search)
58 private int lowerBound(int[] days, int targetDay) {
59 int left = 0, right = days.length;
60 while (left < right) {
61 int mid = left + (right - left) / 2;
62
63 // If mid is less than target, ignore the left half
64 if (days[mid] < targetDay) {
65 left = mid + 1;
66 } else {
67 // If mid is greater or equal to target, ignore the right half
68 right = mid;
69 }
70 }
71 // Return the lower bound index
72 return left;
73 }
74}
751#include <vector>
2#include <algorithm>
3#include <climits>
4
5using namespace std;
6
7class Solution {
8public:
9 vector<int> ticketDurations = {1, 7, 30}; // Durations of tickets in days
10 vector<int> travelDays; // Days on which the person is traveling
11 vector<int> ticketCosts; // Costs corresponding to tickets of each duration
12 vector<int> dpCache; // Cache for storing results of subproblems
13 int totalDays; // Total number of travel days
14
15 // Calculates the minimum cost of all tickets needed for traveling on specific days
16 int mincostTickets(vector<int>& days, vector<int>& costs) {
17 totalDays = days.size(); // Set the total number of travel days
18 this->travelDays = days; // Copy travel days to member variable
19 this->ticketCosts = costs; // Copy ticket costs to member variable
20 dpCache.assign(totalDays, -1); // Initialize the cache with -1, indicating uncomputed states
21 return dfs(0); // Start the DFS traversal from day index 0
22 }
23
24 // Depth-First Search function to calculate the minimum cost of tickets starting from day index 'i'
25 int dfs(int i) {
26 if (i >= totalDays) return 0; // If all travel days are covered, no more cost is needed
27 if (dpCache[i] != -1) return dpCache[i]; // If result is already computed, return it
28
29 int minCost = INT_MAX; // Initialize the minimum cost to max value as we are looking for the minimum
30 for (int k = 0; k < 3; ++k) { // Iterate over the three types of tickets
31 // Find the next travel day index which is outside the current ticket duration
32 int j = lower_bound(travelDays.begin(), travelDays.end(), travelDays[i] + ticketDurations[k]) - travelDays.begin();
33 // Calculate cost and find minimum cost by trying all ticket types
34 minCost = min(minCost, ticketCosts[k] + dfs(j));
35 }
36 dpCache[i] = minCost; // Store the result in the cache before returning
37 return minCost; // Return the minimum cost for tickets starting from day index 'i'
38 }
39};
401function mincostTickets(days: number[], costs: number[]): number {
2 const totalDays = days.length; // Number of days you are traveling
3 const lastDay = days[totalDays - 1] + 1; // The last day of travel (plus one for indexing purposes)
4 const [cost1DayPass, cost7DayPass, cost30DayPass] = costs; // Destructure costs array to name the individual pass costs
5 let dp: number[] = new Array(lastDay).fill(0); // Dynamic programming array to store minimum costs up to each day
6
7 // Iterate over each day in the dp array
8 for (let day = 1; day < lastDay; day++) {
9 // If the current day is among the travel days, we need to consider it for cost calculation
10 let costIfBuy1DayPass = days.includes(day) ? dp[day - 1] + cost1DayPass : dp[day - 1];
11 let costIfBuy7DayPass = (day > 7 ? dp[day - 7] : dp[0]) + cost7DayPass;
12 let costIfBuy30DayPass = (day > 30 ? dp[day - 30] : dp[0]) + cost30DayPass;
13
14 // The minimum cost up to the current day will be the least of the costs using any of the passes
15 dp[day] = Math.min(costIfBuy1DayPass, costIfBuy7DayPass, costIfBuy30DayPass);
16 }
17
18 // Return the minimum cost on the last day of travel
19 return dp[lastDay - 1];
20}
21Which technique can we use to find the middle of a linked list?
Time and Space Complexity
The provided Python code is designed to find the minimum cost of buying tickets for a set of travel days, and the solution involves dynamic programming with memoization (@cache) and binary search (bisect_left).
Time Complexity
The time complexity of the algorithm is primarily governed by the calls to the function dfs. This recursive function is enhanced with memoization, which ensures that each of the N days is processed only once. Inside dfs, a binary search is performed thrice (once for each ticket type) using Python's bisect_left. This takes O(log N) time for each call. Since memoization ensures that each day is processed only once and there are 3 choices for the type of ticket at each day, the number of times bisect_left is called is 3N.
Hence, the overall time complexity is O(N * 3 * log N), which can be simplified to O(N log N).
Space Complexity
The space complexity is determined by the storage required for memoization and the stack space used by recursive calls. The memoization (@cache) will store results for each of the N days, which gives us a space complexity of O(N) for memoization.
As for the recursion stack, in the worst case, the depth will be N (if every day is a travel day and we can buy a ticket for each single day), so the space complexity due to recursion is also O(N).
Thus, the total space complexity of the algorithm is O(N) (where the constants are ignored, and the larger term is considered).
Learn more about how to find time and space complexity quickly using problem constraints.
What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.