Skip to main content
Talentd

Minimum Cost For Tickets - Solution & Explanation

MediumArrayDynamic Programming25 min readAsked at: Amazon, Microsoft, Meta +9
Practice this problem

Problem Statement

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 for 7 days: 2, 3, 4, 5, 6, 7, and 8.

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 <= 365
  • 1 <= days[i] <= 365
  • days is in strictly increasing order.
  • costs.length == 3
  • 1 <= 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.

The C code initializes a dynamic programming (DP) array where each index represents the cost to travel up to that day. For each given travel day, it computes the minimum cost considering each type of pass (1-day, 7-day, 30-day) and stores the result in the DP array.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) where n is the last travel day. Space Complexity: O(n) for the DP array.

Try this approach in the editor →

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.

This C implementation uses recursive depth-first search (DFS) with memoization to explore and store results of subproblems, reducing redundant calculations. The function calculates the minimum cost by considering costs of possible travel passes starting at each travel day index.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) where n is the number of travel days due to memoization. Space Complexity: O(n) for the memo array.

Try this approach in the editor →

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, return 0;
  • 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 j of the next trip, then recursively call dfs(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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming Approach

Time Complexity: O(n) where n is the last travel day. Space Complexity: O(n) for the DP array.

Recursive with Memoization Approach

Time Complexity: O(n) where n is the number of travel days due to memoization. Space Complexity: O(n) for the memo array.

Memoization Search + Binary Search—
Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive with MemoizationO(n)O(n)When deriving the solution from a recursive decision tree and converting it to DP
Bottom-Up Dynamic ProgrammingO(n)O(n)Preferred interview solution with iterative state transitions and no recursion overhead

Video Solution

Minimum Cost for Tickets - Dynamic Programming - Leetcode 983 - Python • NeetCode • 87,468 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Minimum Cost For Tickets with our built-in code editor and test cases.

Practice on FleetCode
Previous

Coin Change

Next

Most Expensive Item That Can Not Be Bought