Abstract / Summary

Find the least expense to travel on specific days using one of three ticket types with different durations and costs.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 65% (400k+ submissions).

Typical patterns to solve this problem:

• Array
• Dynamic Programming

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The program implements a dynamic-programming solution that determines the cheapest combination of single-day, 7-day, and 30-day travel tickets needed to cover a set of travel dates. The entry point is mincostTickets, which prepares the data and invokes a recursive helper dp. The helper explores the three ticket choices at each uncovered travel day, uses memoization to avoid repeated work, and returns the minimal total cost.

Core Components

The class stores the three ticket prices, a copy of the travel dates, and a cache for memoization.

class Solution {
    int single, week, month;
    vector<int> travel;
    unordered_map<int, int> cache;
    …
};

single, week, and month hold the costs for the respective tickets. travel is a sorted list of the days on which travel occurs. cache maps a starting day (from) to the cheapest additional cost needed from that point onward.

Main Algorithm (mincostTickets)

The public method receives the raw travel days and ticket costs, copies and sorts the days, clears any previous cache, and launches the recursion.

int mincostTickets(vector<int>& days, vector<int>& costs) {
    single = costs[0];
    week   = costs[1];
    month  = costs[2];

    travel = days;
    sort(travel.begin(), travel.end());

    cache.clear();

    return dp(0, 0);
}

Sorting guarantees that binary search (lower_bound) can locate the next travel day efficiently. The initial call starts from day 0 with no amount paid yet.

Recursive DP Function (dp)

The heart of the solution is a depth-first search that evaluates the three ticket options at each uncovered travel day.

int dp(int from, int paid)
{
    if (cache.count(from) > 0)
        return cache[from] + paid;

    auto i = lower_bound(travel.begin(), travel.end(), from);
    if (i == travel.end())
        return paid;

    auto next = *i;

    auto s = dp(next +  1, paid + single);
    auto w = dp(next +  7, paid + week);
    auto m = dp(next + 30, paid + month);

    auto result = min(min(s,w),m);

    cache[from] = result - paid;
    return result;
}

The function first checks the cache; if a result for from exists, it adds the already-paid amount and returns immediately. lower_bound finds the first travel day that is not earlier than from. If no such day exists, all travel has been covered and the current paid amount is the final cost.

When a travel day (next) is found, the function recursively explores three scenarios: buying a single-day ticket (advancing to next+1), a weekly ticket (advancing to next+7), or a monthly ticket (advancing to next+30). Each recursive call adds the corresponding ticket price to paid. The minimum of the three outcomes becomes the optimal cost from this state. The difference between that optimal cost and the amount already paid is stored in cache[from] so that future calls starting from the same from can reuse the result without recomputing the sub-problems.

Edge Cases Handled

When the input days vector is empty, the sorted travel list is also empty. The first call to dp immediately hits the i == travel.end() condition and returns paid, which is zero, correctly indicating no cost is required.

If the recursion reaches a from value that lies beyond the last travel day, lower_bound again yields travel.end(), causing the function to terminate the current branch with the accumulated paid amount. This ensures that overshooting the schedule (for example, after buying a 30-day ticket that extends past the final travel day) does not incur extra cost.

The memoization key is the raw from value, not the index in the travel vector. This design gracefully handles cases where multiple travel days are clustered together; the same from may be reached via different ticket choices, and the cached result guarantees consistent handling.

Performance Optimizations

The solution achieves efficiency through three main techniques.

First, the use of an unordered_map for cache provides constant-time look-ups for previously solved sub-problems, eliminating exponential blow-up that a naïve recursive solution would suffer.

Second, sorting the travel days once and then applying lower_bound (binary search) each time the recursion needs the next uncovered day reduces the search from linear to logarithmic time per call.

Third, the recursion passes the cumulative amount already paid (paid) and stores only the incremental cost (result - paid) in the cache. This avoids recomputing the sum of ticket prices for overlapping sub-problems and keeps the cached values small and directly reusable.

Together, these optimizations ensure that each distinct from value is processed at most once, and each processing step performs only a binary search and three constant-time recursive calls, leading to a fast solution even for large input sets.

Imagine you are planning a long train trip and you need to keep track of all the days you want to travel. You have three types of tickets to choose from. One ticket lets you travel for just one day, another covers you for a whole week, and the biggest one lets you ride for an entire month.

The computer starts looking at the first day you want to travel and asks itself a question. It imagines what would happen if it bought the one-day ticket, or the week ticket, or the month ticket. Because the computer can look into the future, it tries all three options to see which one costs the least amount of money in the end.

To make sure the computer does not get tired or do the same math over and over, it keeps a notebook called a cache. Whenever it finds the best way to pay for a trip starting on a certain day, it writes that answer down in the notebook. If it ever needs to figure out the plan for that same day again, it just peeks at the notebook instead of thinking about it from scratch.

The computer marches through all your travel days, carefully picking the cheapest ticket at every step until it reaches the end of your trip. By comparing all these different choices, it finds the absolute best way to pay for all your train rides.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java	Python					TS
	WalkCCC	C++	Java	Python
	leetcode.ca	C++	Java	Python				Go	TS
	LeetcodeHelp	C++	Java	Python
	Progiez	C++	Java	Python
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai		Java
	everthis				JS
	fsq	C++
	Garvit244			Python
	gouthampradhan		Java
	haoel	C++
	JoshCrozier				JS
	keineahnung2345	C++
	lkwq007			Python
	Shamik07						Dart
	suxrobGM					C#
	trung-hn			Python
	varunu28		Java
	vthwang		Java
	wisdompeak	C++
	XiaotaoGuo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
Garvit244	Python
gouthampradhan	Java
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
Shamik07	Dart
suxrobGM	C#
trung-hn	Python
varunu28	Java
vthwang	Java
wisdompeak	C++
XiaotaoGuo	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality