983. Minimum Cost For Tickets - Explanation

Description

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

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Recursion

Intuition

We need to cover all travel days with the minimum cost using 1-day, 7-day, or 30-day passes. At each travel day, we have three choices: buy a 1-day pass (covers today), buy a 7-day pass (covers 7 days starting today), or buy a 30-day pass (covers 30 days starting today). We try all possibilities recursively and pick the minimum cost.

Algorithm

Define a recursive function dfs(i) that returns the minimum cost to cover all days starting from index i.
Base case: If i equals the number of travel days, return 0 (no more days to cover).
For each pass type (1-day, 7-day, 30-day):
- Find the next day index j that is not covered by this pass.
- Calculate the cost as the pass price plus dfs(j).
Return the min cost among all three options.

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

        def dfs(i):
            if i == n:
                return 0

            res = costs[0] + dfs(i + 1)
            j = i
            while j < n and days[j] < days[i] + 7:
                j += 1
            res = min(res, costs[1] + dfs(j))

            j = i
            while j < n and days[j] < days[i] + 30:
                j += 1
            res = min(res, costs[2] + dfs(j))

            return res

        return dfs(0)

Time & Space Complexity

Time complexity: $O(3 ^ n)$
Space complexity: $O(n)$ for recursion stack.

2. Dynamic Programming (Top-Down)

Intuition

The recursive solution recomputes the same subproblems many times. Since the minimum cost from day i onward depends only on i, we can cache these results. This transforms our exponential solution into a linear one by ensuring each state is computed only once.

Algorithm

Create a memoization dictionary dp to store computed results.
Define dfs(i) that returns the minimum cost from index i.
If i is already in dp, return the cached value.
For each pass duration (1, 7, 30 days):
- Find the first uncovered day index j.
- Update the minimum cost as min(current_min, cost + dfs(j)).
Store and return the result.

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        dp = {}

        def dfs(i):
            if i == len(days):
                return 0
            if i in dp:
                return dp[i]

            dp[i] = float("inf")
            j = i
            for d, c in zip([1, 7, 30], costs):
                while j < len(days) and days[j] < days[i] + d:
                    j += 1
                dp[i] = min(dp[i], c + dfs(j))

            return dp[i]

        return dfs(0)

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Dynamic Programming (Bottom-Up)

Intuition

Instead of recursing from day 0 forward, we can build the solution backwards. Starting from the last travel day, we compute the minimum cost for each position. When we reach day 0, we have the answer. This eliminates recursion overhead and makes the solution iterative.

Algorithm

Create a DP array where dp[i] represents the minimum cost from day index i to the end.
Initialize dp[n] = 0 (no cost after the last day).
Iterate from i = n - 1 down to 0.
For each pass type, find where coverage ends and compute cost + dp[j].
Set dp[i] to the min of all options.
Return dp[0].

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

        for i in range(n - 1, -1, -1):
            dp[i] = float('inf')
            j = i
            for d, c in zip([1, 7, 30], costs):
                while j < n and days[j] < days[i] + d:
                    j += 1
                dp[i] = min(dp[i], c + dp[j])

        return dp[0]

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

4. Dynamic Programming (Bottom-Up) + Two Pointers

Intuition

In the previous approach, we search for coverage boundaries repeatedly. Since we iterate backwards and the days array is sorted, we can maintain two pointers that track where 7-day and 30-day passes would end. As we move backwards, these pointers only need to move backwards as well, avoiding redundant searches.

Algorithm

Append a sentinel day to handle boundary conditions.
Initialize pointers last7 and last30 at the end of the array.
Iterate backwards through travel days.
For 7-day and 30-day passes, move the respective pointer backwards while it points to a covered day.
Compute the min of: 1-day pass cost, 7-day pass + dp[last7], and 30-day pass + dp[last30].
Return dp[0].

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        days.append(days[-1] + 30)
        n = len(days)
        dp = [0] * n
        last7 = last30 = n

        for i in range(n - 2, -1, -1):
            dp[i] = dp[i + 1] + costs[0]

            while last7 > i + 1 and days[last7 - 1] >= days[i] + 7:
                last7 -= 1
            dp[i] = min(dp[i], costs[1] + dp[last7])

            while last30 > i + 1 and days[last30 - 1] >= days[i] + 30:
                last30 -= 1
            dp[i] = min(dp[i], costs[2] + dp[last30])

        return dp[0]

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

5. Dynamic Programming (Space Optimized) - I

Intuition

We can process days forward instead of backward. At each day, we only need to know the minimum cost to reach that day using passes bought on earlier days. We use two queues to track when 7-day and 30-day passes expire. Passes that have expired (started more than 7 or 30 days ago) are removed from consideration.

Algorithm

Use two queues to store (day, cost) pairs for 7-day and 30-day passes.
For each travel day:
- Remove expired passes from both queues.
- Add new pass options: buying a 7-day or 30-day pass today.
- Calculate minimum cost: 1-day pass from yesterday, or cheapest valid 7-day or 30-day pass.
Return the final cost after processing all days.

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        dp7, dp30 = deque(), deque()
        dp = 0

        for d in days:
            while dp7 and dp7[0][0] + 7 <= d:
                dp7.popleft()

            while dp30 and dp30[0][0] + 30 <= d:
                dp30.popleft()

            dp7.append([d, dp + costs[1]])
            dp30.append([d, dp + costs[2]])
            dp = min(dp + costs[0], dp7[0][1], dp30[0][1])

        return dp

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ since we keep at most $30$ values in the queue.

6. Dynamic Programming (Space Optimized) - II

Intuition

Similar to the previous approach but processing backwards. We use deques to track costs for 7-day and 30-day passes. As we move backwards, we pop entries that would now be within coverage range of the current day, keeping track of the last popped cost which represents the best option for that pass type.

Algorithm

Use two deques for 7-day and 30-day pass tracking.
Process days from last to first.
Add the 1-day pass cost to the running total.
For 7-day and 30-day passes, pop entries that fall within range and track the best cost.
Take the minimum of all three options.
Add the current day and cost to both deques.

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        dp7, dp30 = deque(), deque()
        dp = 0

        last7 = last30 = 0
        for i in range(len(days) - 1, -1, -1):
            dp += costs[0]
            while dp7 and dp7[-1][0] >= days[i] + 7:
                last7 = dp7.pop()[1]
            dp = min(dp, costs[1] + last7)

            while dp30 and dp30[-1][0] >= days[i] + 30:
                last30 = dp30.pop()[1]
            dp = min(dp, costs[2] + last30)

            dp7.appendleft([days[i], dp])
            dp30.appendleft([days[i], dp])

        return dp

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ since we keep at most $30$ values in the deque.

7. Dynamic Programming (Space Optimized) - III

Intuition

Instead of indexing by travel day positions, we can index by actual calendar days (1 to 365). For non-travel days, the cost stays the same as the previous day. For travel days, we consider all three pass options. This approach is efficient when travel days are sparse across the year.

Algorithm

Create a DP array of size 366 for each day of the year.
Keep a pointer i to track the current travel day index.
For each calendar day from 1 to 365:
- If not a travel day, copy the previous day's cost.
- If it is a travel day, compute the minimum of:
  - dp[d-1] + cost[0] (1-day pass)
  - dp[max(0, d-7)] + cost[1] (7-day pass)
  - dp[max(0, d-30)] + cost[2] (30-day pass)
Return the cost at the last travel day.

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        dp = [0] * 366
        i = 0

        for d in range(1, 366):
            dp[d] = dp[d - 1]
            if i == len(days):
                return dp[d]

            if d == days[i]:
                dp[d] += costs[0]
                dp[d] = min(dp[d], costs[1] + dp[max(0, d - 7)])
                dp[d] = min(dp[d], costs[2] + dp[max(0, d - 30)])
                i += 1

        return dp[365]

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ since the size of the $dp$ array is $366$ .

8. Dynamic Programming (Space Optimized) - IV

Intuition

The previous approach uses 366 slots, but we only ever look back at most 30 days. By using modular arithmetic with a size-31 array, we can reduce space to constant while still accessing the necessary previous states. The index d % 31 ensures we have access to all values within the 30-day window.

Algorithm

Create a DP array of size 31.
For each calendar day, use modular indexing d % 31.
For non-travel days, copy from (d - 1) % 31.
For travel days, compute the minimum using modular indices for lookback.
Return dp[last_travel_day % 31].

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        dp = [0] * 31
        i = 0

        for d in range(1, 366):
            if i >= len(days):
                break

            dp[d % 31] = dp[(d - 1) % 31]

            if d == days[i]:
                dp[d % 31] += costs[0]
                dp[d % 31] = min(dp[d % 31], costs[1] + dp[max(0, d - 7) % 31])
                dp[d % 31] = min(dp[d % 31], costs[2] + dp[max(0, d - 30) % 31])
                i += 1

        return dp[days[-1] % 31]

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ since the size of the $dp$ array is $31$ .

Common Pitfalls

Misunderstanding Pass Duration Coverage

A 7-day pass bought on day d covers days d through d+6 (inclusive), not d+1 through d+7. Similarly, a 30-day pass covers days d through d+29. When finding the next uncovered day, check if days[j] < days[i] + duration, not days[j] <= days[i] + duration. This off-by-one error leads to passes covering one fewer day than they should.

Not Considering All Three Pass Options at Each Decision Point

At each travel day, you must consider all three pass types: 1-day, 7-day, and 30-day. Some solutions greedily choose based on the number of upcoming travel days, but this can be suboptimal. For example, a 7-day pass might be cheaper than seven 1-day passes even if you only travel twice in that week. Always compute and compare the cost of all three options.

Incorrect Base Case or Boundary Handling

When using bottom-up DP, ensure dp[n] = 0 (no cost needed after all travel days). When looking back for pass coverage (e.g., dp[max(0, d-7)]), handle negative indices by clamping to 0. Failing to properly initialize boundaries or handle edge cases like single-day trips or consecutive travel days can produce incorrect results.