Minimum Cost For Tickets solution and explanation
Google
9 more videos on this problem
Minimum Cost for Tickets - Dynamic Programming - Leetcode 983 - PythonNeetCode · 20:03 · 87K views
Minimum Cost For Tickets | Recursion | Memo | Bottom Up | Leetcode-983 | codestorywithMIKcodestorywithMIK · 46:27 · 18K views
Minimum Cost For Tickets - Leetcode 983 - PythonNeetCodeIO · 22:46 · 13K views
983. Minimum Cost For Tickets || Recursion - DP - DP Optimized || C++/Java/PythonAryan Mittal · 22:33 · 4K views
LeetCode 983. Minimum Cost For Tickets Explanation and Solutionhappygirlzt · 8:19 · 4K views
Minimum Cost For Tickets | Leetcode 983Techdose · 20:31 · 3K views
Minimum Cost For Tickets | Leetcode - 983Algorithms Made Easy · 7:28 · 3K views
Minimum Cost For Tickets | Leet code 983 | Theory explained + Python codeSai Anish Malla · 16:39 · 1K views
983. Minimum Cost For Tickets - LeetCode Python SolutionCode with Carter · 10:37 · 648 views
LeetCode 983. Minimum Cost For TicketsHappy Coding · 28:02 · 440 views
The problem
You have planned some train traveling one year in advance. The days of the year in which you will travel are given as an integer array days. Each day is an integer from 1 to 365.
Train tickets are sold in three different ways:
- a 1-day pass is sold for
costs[0]dollars, - a 7-day pass is sold for
costs[1]dollars, and - a 30-day pass is sold for
costs[2]dollars.
The passes allow that many days of consecutive travel.
- For example, if we get a 7-day pass on day
2, then we can travel for7days:2,3,4,5,6,7, and8.
Return the minimum number of dollars you need to travel every day in the given list of days.
Example 1:
Input: days = [1,4,6,7,8,20], costs = [2,7,15] Output: 11 Explanation: For example, here is one way to buy passes that lets you travel your travel plan: On day 1, you bought a 1-day pass for costs[0] = $2, which covered day 1. On day 3, you bought a 7-day pass for costs[1] = $7, which covered days 3, 4, ..., 9. On day 20, you bought a 1-day pass for costs[0] = $2, which covered day 20. In total, you spent $11 and covered all the days of your travel.
Example 2:
Input: days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15] Output: 17 Explanation: For example, here is one way to buy passes that lets you travel your travel plan: On day 1, you bought a 30-day pass for costs[2] = $15 which covered days 1, 2, ..., 30. On day 31, you bought a 1-day pass for costs[0] = $2 which covered day 31. In total, you spent $17 and covered all the days of your travel.
Constraints:
1 <= days.length <= 3651 <= days[i] <= 365daysis in strictly increasing order.costs.length == 31 <= costs[i] <= 1000
Approach overview
Problem Overview: You are given a list of travel days and ticket costs for 1-day, 7-day, and 30-day passes. Each pass covers consecutive days starting from the purchase date. The goal is to choose passes so every travel day is covered while minimizing the total cost.
Approach 1: Recursive with Memoization (Top-Down DP) (Time: O(n), Space: O(n))
This approach treats the problem as a decision tree. For each travel day index i, you decide whether to buy a 1-day, 7-day, or 30-day pass. After choosing a pass, skip forward to the next uncovered travel day using iteration over the days array. A memoization table stores the minimum cost starting from index i, preventing repeated work. Each state is computed once, and the recursion explores three options per state.
The key insight: the optimal decision for day i only depends on the minimum cost of future travel days. Memoization converts the exponential brute-force recursion into linear time by caching results. This pattern is common in dynamic programming problems where decisions affect future states.
Approach 2: Dynamic Programming (Bottom-Up) (Time: O(n), Space: O(n))
The bottom-up version builds the answer iteratively. Define dp[i] as the minimum cost required to cover travel days starting from index i. Process the array from the end toward the beginning. For each index, compute three candidate costs: buy a 1-day pass and move to i+1, buy a 7-day pass and advance until the first day outside the 7-day window, or buy a 30-day pass and advance similarly.
Each step scans forward to locate the next uncovered travel day, then combines the ticket cost with the already-computed future cost. The recurrence becomes dp[i] = min(cost1 + dp[next1], cost7 + dp[next7], cost30 + dp[next30]). Since each travel day is processed once and the array is traversed sequentially, the total time stays linear.
The solution relies on simple iteration over an array and optimal substructure from dynamic programming. No complex data structures are required.
Recommended for interviews: The bottom-up dynamic programming approach is typically preferred. It demonstrates strong understanding of state transitions, avoids recursion overhead, and clearly shows how future costs influence current decisions. Explaining the recursive memoized version first helps show the progression from brute-force thinking to an optimized DP formulation.
Approach 1: Dynamic Programming Approach
This approach uses dynamic programming to maintain a cost array where each cell represents the minimum cost to travel up to that day. For each travel day, you decide to either buy a 1-day, 7-day, or 30-day pass and record the cost accordingly.
def mincostTickets(days, costs):
travel_days = set(days)
dp = [0] * (days[-1] + 1)
for i in range(1, days[-1] + 1):
if i not in travel_days:
dp[i] = dp[i - 1]
else:
dp[i] = min(dp[i - 1] + costs[0],
dp[i - 7] + costs[1] if i >= 7 else costs[1],
dp[i - 30] + costs[2] if i >= 30 else costs[2])
return dp[-1]
# Example Usage
print(mincostTickets([1,4,6,7,8,20], [2,7,15])) # Output: 11import java.util.HashSet;
import java.util.Set;
class Solution {
public int mincostTickets(int[] days, int[] costs) {
Set<Integer> daySet = new HashSet<>();
for (int day : days) daySet.add(day);
int[] dp = new int[366];
for (int i = 1; i < 366; i++) {
if (!daySet.contains(i)) {
dp[i] = dp[i - 1];
} else {
dp[i] = Math.min(dp[i - 1] + costs[0],
Math.min(dp[Math.max(0, i - 7)] + costs[1],
dp[Math.max(0, i - 30)] + costs[2]));
}
}
return dp[365];
}
}#include <vector>
#include <algorithm>
class Solution {
public:
int mincostTickets(std::vector<int>& days, std::vector<int>& costs) {
int n = days.back();
std::vector<int> dp(n + 1, 0);
std::vector<bool> travelDay(n + 1, false);
for (int day : days) travelDay[day] = true;
for (int i = 1; i <= n; i++) {
if (!travelDay[i]) {
dp[i] = dp[i - 1];
} else {
dp[i] = std::min({
dp[i - 1] + costs[0],
dp[i - 7 < 0 ? 0 : i - 7] + costs[1],
dp[i - 30 < 0 ? 0 : i - 30] + costs[2]
});
}
}
return dp[n];
}
};function mincostTickets(days, costs) {
let lastDay = days[days.length - 1];
let dp = new Array(lastDay + 1).fill(0);
let dayIndex = new Set(days);
for (let i = 1; i <= lastDay; i++) {
if (!dayIndex.has(i)) {
dp[i] = dp[i - 1];
} else {
dp[i] = Math.min(
dp[i - 1] + costs[0],
(dp[i - 7] || 0) + costs[1],
(dp[i - 30] || 0) + costs[2]
);
}
}
return dp[lastDay];
}
console.log(mincostTickets([1,4,6,7,8,20], [2,7,15])); // Output: 11#include <stdio.h>
int mincostTickets(int* days, int daysSize, int* costs, int costsSize) {
int n = days[daysSize - 1];
int dp[n + 1];
int dayIndex = 0;
for (int i = 0; i <= n; i++) dp[i] = 0;
for (int i = 1; i <= n; i++) {
if (i != days[dayIndex]) {
dp[i] = dp[i - 1];
} else {
int oneDayPass = dp[i - 1] + costs[0];
int sevenDayPass = dp[(i - 7 >= 0) ? i - 7 : 0] + costs[1];
int thirtyDayPass = dp[(i - 30 >= 0) ? i - 30 : 0] + costs[2];
dp[i] = oneDayPass < sevenDayPass ? oneDayPass : sevenDayPass;
dp[i] = dp[i] < thirtyDayPass ? dp[i] : thirtyDayPass;
dayIndex++;
}
}
return dp[n];
}
int main() {
int days[] = {1, 4, 6, 7, 8, 20};
int costs[] = {2, 7, 15};
int result = mincostTickets(days, 6, costs, 3);
printf("The minimum cost to travel is %d\n", result);
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int MincostTickets(int[] days, int[] costs) {
var travelDays = new HashSet<int>(days);
int[] dp = new int[366];
for (int i = 1; i <= 365; i++) {
if (!travelDays.Contains(i)) {
dp[i] = dp[i - 1];
} else {
dp[i] = Math.Min(
dp[i - 1] + costs[0],
Math.Min(dp[Math.Max(0, i - 7)] + costs[1],
dp[Math.Max(0, i - 30)] + costs[2])
);
}
}
return dp[365];
}
}Python follows a similar approach as the other implementations, using a set to quickly identify travel days. The dynamic programming array holds the cumulative cost to travel up to the current day.
Time Complexity: O(n) where n is the maximum travel day. Space Complexity: O(n) to store the DP costs.
Approach 2: Recursive with Memoization Approach
This approach uses recursion with memoization to explore each travel day recursively, storing intermediate results to avoid redundant calculations. It offers a top-down perspective on decision-making for ticket purchasing.
def mincostTickets(days, costs):
memo = [-1] * len(days)
def dfs(i):
if i >= len(days):
return 0
if memo[i] != -1:
return memo[i]
j = i
# 1-day pass
cost_1 = costs[0] + dfs(i + 1)
# 7-day pass
while j < len(days) and days[j] < days[i] + 7:
j += 1
cost_7 = costs[1] + dfs(j)
# 30-day pass
while j < len(days) and days[j] < days[i] + 30:
j += 1
cost_30 = costs[2] + dfs(j)
memo[i] = min(cost_1, cost_7, cost_30)
return memo[i]
return dfs(0)
# Example Usage
print(mincostTickets([1, 4, 6, 7, 8, 20], [2, 7, 15])) # Output: 11import java.util.Arrays;
class Solution {
private int[] memo;
private int[] days, costs;
public int mincostTickets(int[] days, int[] costs) {
this.days = days;
this.costs = costs;
memo = new int[days.length];
Arrays.fill(memo, -1);
return dfs(0);
}
private int dfs(int i) {
if (i >= days.length) return 0;
if (memo[i] != -1) return memo[i];
int j = i;
int oneDay = costs[0] + dfs(i + 1);
while (j < days.length && days[j] < days[i] + 7) j++;
int sevenDay = costs[1] + dfs(j);
while (j < days.length && days[j] < days[i] + 30) j++;
int thirtyDay = costs[2] + dfs(j);
return memo[i] = Math.min(oneDay, Math.min(sevenDay, thirtyDay));
}
}#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
class Solution {
int memo[366];
public:
int dfs(vector<int>& days, vector<int>& costs, int i) {
if (i >= days.size()) return 0;
if (memo[i] != -1) return memo[i];
int oneDay = costs[0] + dfs(days, costs, i + 1);
int j;
for (j = i; j < days.size() && days[j] < days[i] + 7; j++);
int sevenDay = costs[1] + dfs(days, costs, j);
for (j = i; j < days.size() && days[j] < days[i] + 30; j++);
int thirtyDay = costs[2] + dfs(days, costs, j);
return memo[i] = min(oneDay, min(sevenDay, thirtyDay));
}
int mincostTickets(vector<int>& days, vector<int>& costs) {
memset(memo, -1, sizeof(memo));
return dfs(days, costs, 0);
}
};function mincostTickets(days, costs) {
const memo = new Array(days.length).fill(-1);
function dfs(i) {
if (i >= days.length) return 0;
if (memo[i] !== -1) return memo[i];
const oneDay = costs[0] + dfs(i + 1);
let j = i;
while (j < days.length && days[j] < days[i] + 7) j++;
const sevenDay = costs[1] + dfs(j);
while (j < days.length && days[j] < days[i] + 30) j++;
const thirtyDay = costs[2] + dfs(j);
memo[i] = Math.min(oneDay, sevenDay, thirtyDay);
return memo[i];
}
return dfs(0);
}
console.log(mincostTickets([1, 4, 6, 7, 8, 20], [2, 7, 15])); // Output: 11#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int dfs(int *days, int daysSize, int *costs, int start, int* memo) {
if (start >= daysSize) return 0;
if (memo[start] != -1) return memo[start];
int oneDay = costs[0] + dfs(days, daysSize, costs, start + 1, memo);
int i;
for (i = start; i < daysSize && days[i] < days[start] + 7; i++);
int sevenDay = costs[1] + dfs(days, daysSize, costs, i, memo);
for (i = start; i < daysSize && days[i] < days[start] + 30; i++);
int thirtyDay = costs[2] + dfs(days, daysSize, costs, i, memo);
return memo[start] = fmin(oneDay, fmin(sevenDay, thirtyDay));
}
int mincostTickets(int* days, int daysSize, int* costs, int costsSize) {
int memo[daysSize];
memset(memo, -1, sizeof(memo));
return dfs(days, daysSize, costs, 0, memo);
}
int main() {
int days[] = {1, 4, 6, 7, 8, 20};
int costs[] = {2, 7, 15};
int result = mincostTickets(days, 6, costs, 3);
printf("Minimum cost to travel is %d\n", result);
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
private int[] days;
private int[] costs;
private int[] memo;
public int MincostTickets(int[] days, int[] costs) {
this.days = days;
this.costs = costs;
this.memo = new int[days.Length];
Array.Fill(memo, -1);
return Dfs(0);
}
private int Dfs(int i) {
if (i >= days.Length) return 0;
if (memo[i] != -1) return memo[i];
int oneDay = costs[0] + Dfs(i + 1);
int j = i;
while (j < days.Length && days[j] < days[i] + 7) j++;
int sevenDay = costs[1] + Dfs(j);
while (j < days.Length && days[j] < days[i] + 30) j++;
int thirtyDay = costs[2] + Dfs(j);
return memo[i] = Math.Min(oneDay, Math.Min(sevenDay, thirtyDay));
}
}This Python variant employs recursion combined with memoization for storing intermediate solutions, intending to calculate and conserve the minimum cost of tickets. The recursive helper investigates each travel day to determine which combination of passes yields the least expense.
Time Complexity: O(n) due to memoization preventing repeated calculations. Space Complexity: O(n) because of the conservation of subproblem results in the memoization list.
Approach 3: Memoization Search + Binary Search
We define a function dfs(i), which represents the minimum cost required from the i-th trip to the last trip. Thus, the answer is dfs(0).
The execution process of the function dfs(i) is as follows:
- If
i geq n, it means all trips have ended, return0; - Otherwise, we need to consider three types of purchases: buying a 1-day pass, buying a 7-day pass, and buying a 30-day pass. We calculate the cost for these three purchasing methods separately and use binary search to find the index
jof the next trip, then recursively calldfs(j), and finally return the minimum cost among these three purchasing methods.
To avoid repeated calculations, we use memoization search to save the results that have already been calculated.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n represents the number of trips.
function mincostTickets(days: number[], costs: number[]): number {
const n = days.length;
const f: number[] = Array(n).fill(0);
const valid: number[] = [1, 7, 30];
const search = (x: number): number => {
let [l, r] = [0, n];
while (l < r) {
const mid = (l + r) >> 1;
if (days[mid] >= x) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
};
const dfs = (i: number): number => {
if (i >= n) {
return 0;
}
if (f[i]) {
return f[i];
}
f[i] = Infinity;
for (let k = 0; k < 3; ++k) {
const j = search(days[i] + valid[k]);
f[i] = Math.min(f[i], dfs(j) + costs[k]);
}
return f[i];
};
return dfs(0);
}func mincostTickets(days []int, costs []int) int {
valid := [3]int{1, 7, 30}
n := len(days)
f := make([]int, n)
var dfs func(int) int
dfs = func(i int) int {
if i >= n {
return 0
}
if f[i] > 0 {
return f[i]
}
f[i] = 1 << 30
for k := 0; k < 3; k++ {
j := sort.SearchInts(days, days[i]+valid[k])
f[i] = min(f[i], dfs(j)+costs[k])
}
return f[i]
}
return dfs(0)
}Approach 4: Dynamic Programming
Let's denote the last day in the days array as m. We can define an array f of length m + 1, where f[i] represents the minimum cost from day 1 to day i.
We can calculate the value of f[i] in increasing order of the dates in the days array, starting from day 1. If day i is a travel day, we can consider three purchasing options: buying a 1-day pass, buying a 7-day pass, and buying a 30-day pass. We calculate the cost for these three purchasing methods separately and take the minimum cost among these three as the value of f[i]. If day i is not a travel day, then f[i] = f[i - 1].
The final answer is f[m].
The time complexity is O(m), and the space complexity is O(m). Here, m represents the last day of travel.
function mincostTickets(days: number[], costs: number[]): number {
const m = days.at(-1)!;
const f: number[] = Array(m).fill(0);
const valid: number[] = [1, 7, 30];
for (let i = 1, j = 0; i <= m; ++i) {
if (i === days[j]) {
f[i] = Infinity;
for (let k = 0; k < 3; ++k) {
const [c, v] = [costs[k], valid[k]];
f[i] = Math.min(f[i], f[Math.max(0, i - v)] + c);
}
++j;
} else {
f[i] = f[i - 1];
}
}
return f[m];
}func mincostTickets(days []int, costs []int) int {
m := days[len(days)-1]
f := make([]int, m+1)
valid := [3]int{1, 7, 30}
for i, j := 1, 0; i <= m; i++ {
if i == days[j] {
f[i] = 1 << 30
for k, v := range valid {
c := costs[k]
f[i] = min(f[i], f[max(0, i-v)]+c)
}
j++
} else {
f[i] = f[i-1]
}
}
return f[m]
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n) where n is the maximum travel day. Space Complexity: O(n) to store the DP costs. |
| Recursive with Memoization Approach | Time Complexity: O(n) due to memoization preventing repeated calculations. Space Complexity: O(n) because of the conservation of subproblem results in the memoization list. |
| Memoization Search + Binary Search | – |
| Dynamic Programming | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive with Memoization | O(n) | O(n) | When deriving the solution from a recursive decision tree and converting it to DP |
| Bottom-Up Dynamic Programming | O(n) | O(n) | Preferred interview solution with iterative state transitions and no recursion overhead |
Frequently asked questions
Is Minimum Cost For Tickets easy or hard?
Minimum Cost For Tickets is classified as a Medium problem on LeetCode. The challenge lies in recognizing the dynamic programming pattern and correctly handling the range covered by 7-day and 30-day passes.
Minimum Cost For Tickets Python/Java solution
Python, Java, C++, C#, and JavaScript implementations typically use the same DP logic. Define dp[i] as the minimum cost from the i-th travel day, evaluate three ticket options, and reuse stored results to achieve O(n) complexity.
How to solve Minimum Cost For Tickets in O(n)?
Use dynamic programming over the travel days array. For each index, compute the cost of buying a 1-day, 7-day, or 30-day pass and jump to the next uncovered travel day. Store the minimum cost in a DP array so each state is evaluated only once.
What is the best approach for Minimum Cost For Tickets?
Dynamic programming is the best approach. Model each travel day as a state and compute the minimum cost by choosing between a 1-day, 7-day, or 30-day pass. The bottom-up DP solution runs in O(n) time and O(n) space where n is the number of travel days.
Is Minimum Cost For Tickets asked at Google/Amazon/Meta?
Minimum Cost For Tickets is a common dynamic programming interview problem and variations have appeared in interviews at companies like Amazon and Google. It tests DP state transitions, optimization decisions, and reasoning about overlapping subproblems.
What data structure is used in Minimum Cost For Tickets?
The solution primarily uses an array for the list of travel days and a DP array (or memoization map) to store minimum costs for each state. No advanced data structures are required beyond basic arrays and indexing.
What is the time complexity of Minimum Cost For Tickets?
The optimal dynamic programming solution runs in O(n) time where n is the number of travel days. Each state evaluates three ticket options and advances to the next uncovered day, while previously computed results are reused.