LeetCode 983 - Minimum Cost For Tickets

LeetCode Problem 983

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

Problem Understanding

In this problem, we are given a list of travel days during a single year and the costs of three different train passes. Each pass covers a consecutive range of days:

• A 1-day pass covers exactly one day.
• A 7-day pass covers seven consecutive days.
• A 30-day pass covers thirty consecutive days.

The goal is to determine the minimum total cost required to cover every travel day in the days array.

The input array days is strictly increasing, which means the travel days are already sorted and contain no duplicates. This property is extremely useful because it allows us to process the travel schedule sequentially without worrying about reordering or repeated work.

The costs array always contains exactly three integers:

• costs[0] is the price of a 1-day pass
• costs[1] is the price of a 7-day pass
• costs[2] is the price of a 30-day pass

The important detail is that passes cover consecutive calendar days, not just travel days. For example, if a 7-day pass starts on day 10, it covers days 10 through 16 inclusive, even if we do not travel on some of those days.

The constraints are relatively small:

• At most 365 travel days
• Days range only from 1 to 365

These constraints strongly suggest that dynamic programming is an appropriate solution. Since the total number of days in a year is fixed and small, we can afford solutions that process each day or each travel index efficiently.

Several edge cases are important to consider:

• Only one travel day exists.
• All travel days are consecutive.
• Travel days are very sparse.
• A longer pass may actually be cheaper than repeatedly buying shorter passes.
• Some days may already be covered by a previously purchased pass.

A naive implementation can easily make mistakes when determining which future days are covered by a pass, especially around inclusive boundaries.

Approaches

Brute Force Approach

The brute force solution tries every possible ticket purchase combination.

At each travel day, we can make one of three choices:

1. Buy a 1-day pass
2. Buy a 7-day pass
3. Buy a 30-day pass

After buying a pass, we recursively move to the next uncovered travel day and repeat the process. Eventually, we compute the total cost for every possible combination and return the minimum.

This approach is correct because it exhaustively explores every valid purchasing strategy. However, it repeatedly recomputes the same subproblems. For example, multiple decision paths may eventually ask:

"What is the minimum cost starting from travel day index 10?"

Without memoization, these repeated calculations create exponential growth.

Key Insight for the Optimal Solution

The crucial observation is that the problem has overlapping subproblems and optimal substructure.

Suppose we already know the minimum cost needed to cover all travel days starting from some index i. Then we can use that information to compute the answer for earlier indices.

For each travel day, we only need to consider three possibilities:

• Buy a 1-day pass
• Buy a 7-day pass
• Buy a 30-day pass

After choosing a pass, we jump directly to the first uncovered travel day.

This naturally leads to dynamic programming with memoization.

Instead of recalculating the same states repeatedly, we store previously computed results. Since there are at most 365 travel days, the total number of states is small.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(3^n)	O(n)	Explores all ticket purchase combinations recursively
Optimal	O(n)	O(n)	Dynamic programming with memoization

Algorithm Walkthrough

Optimal Dynamic Programming Strategy

1. Define a recursive function dp(i).

This function represents the minimum cost needed to cover all travel days starting from index i in the days array.

If i reaches the end of the array, there are no remaining travel days, so the cost is 0. 2. At index i, identify the current travel day.

Let:

current_day = days[i]

We now consider buying each type of pass starting on this day. 3. Try buying a 1-day pass.

A 1-day pass only covers the current day.

We move to the next travel day:

cost1 = costs[0] + dp(i + 1)

4. Try buying a 7-day pass.

This pass covers all travel days from:

current_day through current_day + 6

We advance the pointer until we reach the first uncovered travel day. 5. Try buying a 30-day pass.

Similarly, this pass covers:

current_day through current_day + 29

Again, we skip all covered travel days. 6. Take the minimum of the three options.

The optimal solution for index i is:

min(cost1, cost7, cost30)

7. Memoize the result.

Store the computed answer for index i so future calls can reuse it instantly.

Why it works

The algorithm works because every valid travel plan must decide how to cover the current uncovered travel day. There are only three valid ticket choices. For each choice, once the covered range is determined, the remaining problem becomes identical in structure to the original problem, just starting from a later travel day.

Dynamic programming guarantees correctness because each subproblem computes the true minimum cost for its suffix of travel days, and the final answer is built from these optimal subproblem solutions.

Python Solution

from typing import List
from functools import lru_cache

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        n = len(days)

        @lru_cache(None)
        def dp(index: int) -> int:
            if index >= n:
                return 0

            # Option 1: Buy 1-day pass
            cost_1_day = costs[0] + dp(index + 1)

            # Option 2: Buy 7-day pass
            next_index = index
            while next_index < n and days[next_index] < days[index] + 7:
                next_index += 1

            cost_7_day = costs[1] + dp(next_index)

            # Option 3: Buy 30-day pass
            next_index = index
            while next_index < n and days[next_index] < days[index] + 30:
                next_index += 1

            cost_30_day = costs[2] + dp(next_index)

            return min(cost_1_day, cost_7_day, cost_30_day)

        return dp(0)

The implementation closely follows the dynamic programming strategy described earlier.

The dp(index) function computes the minimum cost needed to cover all travel days beginning at index.

The @lru_cache(None) decorator automatically memoizes results, preventing repeated computations for the same index.

For each recursive call, the algorithm evaluates all three pass options:

• The 1-day pass advances exactly one travel day.
• The 7-day pass skips every travel day covered within seven consecutive calendar days.
• The 30-day pass skips every travel day covered within thirty consecutive calendar days.

The while loops are important because travel days are sparse. We do not advance by fixed positions. Instead, we skip all travel days already covered by the selected pass.

Finally, the function returns the minimum among the three possible costs.

Go Solution

func mincostTickets(days []int, costs []int) int {
	n := len(days)

	memo := make(map[int]int)

	var dp func(int) int

	dp = func(index int) int {
		if index >= n {
			return 0
		}

		if value, exists := memo[index]; exists {
			return value
		}

		// Option 1: 1-day pass
		cost1 := costs[0] + dp(index+1)

		// Option 2: 7-day pass
		nextIndex := index
		for nextIndex < n && days[nextIndex] < days[index]+7 {
			nextIndex++
		}

		cost7 := costs[1] + dp(nextIndex)

		// Option 3: 30-day pass
		nextIndex = index
		for nextIndex < n && days[nextIndex] < days[index]+30 {
			nextIndex++
		}

		cost30 := costs[2] + dp(nextIndex)

		result := min(cost1, min(cost7, cost30))

		memo[index] = result

		return result
	}

	return dp(0)
}

func min(a int, b int) int {
	if a < b {
		return a
	}
	return b
}

The Go implementation uses an explicit memoization map instead of Python's lru_cache.

Go does not provide built-in memoization decorators, so we manually store computed results in memo.

The recursive structure and transition logic remain identical to the Python version.

Since the maximum possible answer is small, integer overflow is not a concern in Go.

Worked Examples

Example 1

days = [1,4,6,7,8,20]
costs = [2,7,15]

We start at index 0, corresponding to travel day 1.

Step	Current Day	Pass Chosen	Covered Days	Next Index	Total Cost
1	1	1-day	1	1	2 + future
2	1	7-day	1-7	4	7 + future
3	1	30-day	1-30	6	15

Now compute recursively.

Computing from index 4

Travel day is 8.

Pass	Covers	Next Index	Cost
1-day	8	5	2 + dp(5)
7-day	8-14	5	7 + dp(5)
30-day	8-37	6	15

Computing from index 5

Travel day is 20.

Pass	Covers	Next Index	Cost
1-day	20	6	2
7-day	20-26	6	7
30-day	20-49	6	15

Minimum is 2.

Backtracking:

dp(5) = 2
dp(4) = 4
dp(1) = 9
dp(0) = 11

Final answer:

11

Example 2

days = [1,2,3,4,5,6,7,8,9,10,30,31]
costs = [2,7,15]

At day 1, compare options:

Pass	Coverage	Remaining Travel Days
1-day	1	many remain
7-day	1-7	days 8,9,10,30,31
30-day	1-30	only day 31 remains

The 30-day pass is highly efficient because it covers almost every trip.

Cost breakdown:

Purchase	Cost
30-day pass starting day 1	15
1-day pass for day 31	2
Total	17

Final answer:

17

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each travel index is solved once with memoization
Space	O(n)	Memoization cache and recursion stack

Although each recursive call contains small while loops, every index is processed only once overall. Since n <= 365, the solution is very efficient.

The recursion depth is also bounded by the number of travel days, so the space usage remains linear.

Test Cases

from typing import List

sol = Solution()

# Provided example 1
assert sol.mincostTickets([1,4,6,7,8,20], [2,7,15]) == 11

# Provided example 2
assert sol.mincostTickets(
    [1,2,3,4,5,6,7,8,9,10,30,31],
    [2,7,15]
) == 17

# Single travel day
assert sol.mincostTickets([100], [5,10,20]) == 5

# Consecutive travel days favor longer pass
assert sol.mincostTickets(
    [1,2,3,4,5,6,7],
    [3,8,20]
) == 8

# Entire month of travel
assert sol.mincostTickets(
    list(range(1, 31)),
    [2,7,15]
) == 15

# Sparse travel days favor 1-day passes
assert sol.mincostTickets(
    [1,50,100,150,200],
    [2,20,50]
) == 10

# 30-day pass cheaper than many short passes
assert sol.mincostTickets(
    [1,2,3,4,5,6,7,8,9,10],
    [5,20,21]
) == 21

# Travel days near end of year
assert sol.mincostTickets(
    [350,351,352,353,354,355],
    [3,10,25]
) == 10

# Only two travel days far apart
assert sol.mincostTickets(
    [1,365],
    [2,7,15]
) == 4

# Dense schedule across multiple months
assert sol.mincostTickets(
    [1,2,3,4,5,20,21,22,23,24,40,41],
    [3,9,20]
) == 18

Test	Why
[1,4,6,7,8,20]	Validates standard mixed scheduling
[1,2,3,4,5,6,7,8,9,10,30,31]	Validates long pass efficiency
[100]	Tests smallest possible input
Consecutive 7 days	Ensures 7-day pass selection
Full month travel	Ensures 30-day pass selection
Sparse days	Ensures repeated 1-day passes work
Cheap 30-day pass	Validates optimal cost comparison
End-of-year travel	Tests boundary day values
[1,365]	Tests extremely sparse schedule
Multiple clusters	Tests mixed pass strategies

Edge Cases

Single Travel Day

If there is only one travel day, the optimal solution is almost always the cheapest applicable pass, usually the 1-day pass.

A buggy implementation might still attempt unnecessary recursion or incorrectly compute coverage ranges. Our implementation handles this naturally because the recursion immediately reaches the base case after covering the single day.

Consecutive Travel Days

When many travel days occur back-to-back, longer passes become much more efficient.

For example:

days = [1,2,3,4,5,6,7]

A naive greedy strategy that always buys the cheapest immediate ticket may fail badly here. Our dynamic programming approach evaluates all three pass types at every state, guaranteeing the globally optimal answer.

Sparse Travel Days

When travel days are widely separated, long-duration passes may waste money because most covered days are unused.

For example:

days = [1,100,200,300]

The algorithm correctly handles this because the while loops skip only covered travel days, not calendar days. As a result, each recursive state accurately reflects the next uncovered travel day.