Minimum Cost For Tickets

Medium
332.

Minimum Cost For Tickets

Minimum Cost For Tickets is a medium coding problem on arrays and dynamic programming, asked in Amazon, Google and Uber interviews.

You have planned train travel for a year, given as a sorted array days of the days you will travel, each between 1 and 365.

Tickets come in three kinds, priced by costs = [oneDay, sevenDay, thirtyDay]: a 1-day pass, a 7-day pass and a 30-day pass, each valid for that many consecutive days starting from the day you buy it.

Return the minimum money needed to cover every travel day.

Example 1

Input
days = [1,4,6,7,8,20], costs = [2,7,15]
Output
11
Explanation
A 1-day pass on day 1, a 7-day pass on day 3, and a 1-day pass on day 20.

Example 2

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

Example 3

Input
days = [1], costs = [5,10,20]
Output
5

Constraints

  • 1 <= days.length <= 50
  • 1 <= days[i] <= 365
  • days is strictly increasing.
  • 1 <= costs[i] <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} days
 * @param {number[]} costs
 * @return {number}
 */
var mincostTickets = function(days, costs) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Cost For Tickets — Solution in Python, Java & C++

Minimum Cost For Tickets solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Minimum Cost For Tickets is a medium coding problem on arrays and dynamic programming, asked in Amazon, Google and Uber interviews.

  • Difficulty: Medium
  • Topics: Arrays, Dynamic Programming
  • Asked at: Amazon, Google, Uber
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You have planned train travel for a year, given as a sorted array days of the days you will travel, each between 1 and 365.

Tickets come in three kinds, priced by costs = [oneDay, sevenDay, thirtyDay]: a 1-day pass, a 7-day pass and a 30-day pass, each valid for that many consecutive days starting from the day you buy it.

Return the minimum money needed to cover every travel day.

Example 1

Input: days = [1,4,6,7,8,20], costs = [2,7,15]
Output: 11
Explanation: A 1-day pass on day 1, a 7-day pass on day 3, and a 1-day pass on day 20.

Example 2

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

Example 3

Input: days = [1], costs = [5,10,20]
Output: 5

Constraints

  • 1 <= days.length <= 50
  • 1 <= days[i] <= 365
  • days is strictly increasing.
  • 1 <= costs[i] <= 1000

Hints for Minimum Cost For Tickets

  1. Hint 1

    Work day by day up to the last travel day rather than pass by pass.

  2. Hint 2

    On a non-travel day the cost is unchanged from the day before.

  3. Hint 3

    On a travel day, try all three passes: dp[d-1] + cost1, dp[d-7] + cost7, dp[d-30] + cost30, clamping the index at 0.

How to solve Minimum Cost For Tickets

Work day by day to the last travel day; a non-travel day costs nothing extra, a travel day takes the cheapest of a 1-, 7- or 30-day pass bought to cover it.

Approach

  1. Mark travel days in a boolean array up to days[-1].
  2. For each day d: if not a travel day, dp[d] = dp[d-1]; else dp[d] = min(dp[d-1] + c1, dp[max(0,d-7)] + c7, dp[max(0,d-30)] + c30).
  3. Return dp[last].

Why it works

A pass covering day d can be assumed to end on d without loss, so the cost to cover through d is the cost to cover through the day before the pass started plus the pass price.

Complexity

  • Time — O(365)
  • Space — O(365)

Pitfalls

  • Clamp the index at 0 for passes that would start before day 1.

Reference solution

Python

def mincostTickets(days, costs) -> int:
    last = days[-1]
    travel = [False] * (last + 1)
    for d in days:
        travel[d] = True
    dp = [0] * (last + 1)
    for d in range(1, last + 1):
        if not travel[d]:
            dp[d] = dp[d - 1]
        else:
            dp[d] = min(dp[d - 1] + costs[0],
                        dp[max(0, d - 7)] + costs[1],
                        dp[max(0, d - 30)] + costs[2])
    return dp[last]

Java

public static int mincostTickets(int[] days, int[] costs) {
    int last = days[days.length - 1];
    boolean[] travel = new boolean[last + 1];
    for (int d : days) travel[d] = true;
    int[] dp = new int[last + 1];
    for (int d = 1; d <= last; d++) {
        if (!travel[d]) {
            dp[d] = dp[d - 1];
        } else {
            int one = dp[d - 1] + costs[0];
            int seven = dp[Math.max(0, d - 7)] + costs[1];
            int thirty = dp[Math.max(0, d - 30)] + costs[2];
            dp[d] = Math.min(one, Math.min(seven, thirty));
        }
    }
    return dp[last];
}

C++

int mincostTickets(vector<int>& days, vector<int>& costs) {
    int last = days.back();
    vector<char> travel(last + 1, 0);
    for (int d : days) travel[d] = 1;
    vector<int> dp(last + 1, 0);
    for (int d = 1; d <= last; d++) {
        if (!travel[d]) {
            dp[d] = dp[d - 1];
        } else {
            int one = dp[d - 1] + costs[0];
            int seven = dp[max(0, d - 7)] + costs[1];
            int thirty = dp[max(0, d - 30)] + costs[2];
            dp[d] = min(one, min(seven, thirty));
        }
    }
    return dp[last];
}

JavaScript

var mincostTickets = function(days, costs) {
    const last = days[days.length - 1];
    const travel = new Array(last + 1).fill(false);
    for (let i = 0; i < days.length; i++) travel[days[i]] = true;
    const dp = new Array(last + 1).fill(0);
    for (let d = 1; d <= last; d++) {
        if (!travel[d]) {
            dp[d] = dp[d - 1];
            continue;
        }
        const one = dp[d - 1] + costs[0];
        const seven = dp[Math.max(0, d - 7)] + costs[1];
        const thirty = dp[Math.max(0, d - 30)] + costs[2];
        dp[d] = Math.min(one, Math.min(seven, thirty));
    }
    return dp[last];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming