Scale Engineer

Minimum Cost For Tickets

Med
#0937Time: O(3^N), where N is the number of travel days. At each travel day, the function can branch into three recursive calls, leading to an exponential growth in the number of operations.Space: O(N), where N is the number of travel days. This space is used by the recursion stack.6 companies
Patterns
Dynamic Programming
Data structures
Array
Companies
FlipkartGrabIntuitTuring

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly translates the problem's decision-making process into a recursive function. For each travel day, we explore the three choices of buying a 1-day, 7-day, or 30-day pass. We then recursively calculate the cost for the remaining travel days for each choice and select the one that results in the minimum total cost. This method is intuitive but computationally expensive.

Algorithm

  • Define a recursive function solve(index) that calculates the minimum cost for travel days starting from days[index].
  • The base case: if index is out of bounds (i.e., index >= days.length), it means all travel is covered, so return 0.
  • For the current travel day days[index], recursively explore three choices:
    1. 1-day pass: The cost is costs[0] plus the result of solve(index + 1).
    2. 7-day pass: Find the next travel day index j that is not covered by a pass bought on days[index] (i.e., days[j] > days[index] + 6). The cost is costs[1] plus solve(j).
    3. 30-day pass: Find the next travel day index k such that days[k] > days[index] + 29. The cost is costs[2] plus solve(k).
  • Return the minimum cost among the three options.
  • The final answer is the result of the initial call solve(0).

Walkthrough

We define a helper function, say solve(index), which computes the minimum cost to cover travel days from days[index] onwards. The core of this function is to handle the decision at days[index].

  • Base Case: If index is greater than or equal to days.length, it means we have successfully covered all travel days, and no more cost is needed. We return 0.
  • Recursive Step: For the current travel day days[index], we calculate the cost for each of the three ticket options:
    1. Buy a 1-day pass: This covers days[index]. The cost is costs[0] plus the cost for the rest of the travel plan, which is found by the recursive call solve(index + 1).
    2. Buy a 7-day pass: This pass, bought on days[index], covers all travel for 7 consecutive days (i.e., up to days[index] + 6). We need to find the first travel day that falls after this period. We iterate from index to find the smallest j such that days[j] >= days[index] + 7. The cost is costs[1] plus solve(j).
    3. Buy a 30-day pass: Similarly, this covers travel up to days[index] + 29. We find the smallest k such that days[k] >= days[index] + 30. The cost is costs[2] plus solve(k).

The function then returns the minimum of these three calculated costs. The main function initiates this process by calling solve(0). Because this method re-computes solutions for the same subproblems multiple times, its time complexity is exponential.

class Solution {    private int[] days;    private int[] costs;     public int mincostTickets(int[] days, int[] costs) {        this.days = days;        this.costs = costs;        return solve(0);    }     private int solve(int index) {        if (index >= days.length) {            return 0;        }         // Option 1: 1-day pass        int cost1 = costs[0] + solve(index + 1);         // Option 2: 7-day pass        int nextIndex7 = index;        while (nextIndex7 < days.length && days[nextIndex7] < days[index] + 7) {            nextIndex7++;        }        int cost7 = costs[1] + solve(nextIndex7);         // Option 3: 30-day pass        int nextIndex30 = index;        while (nextIndex30 < days.length && days[nextIndex30] < days[index] + 30) {            nextIndex30++;        }        int cost30 = costs[2] + solve(nextIndex30);         return Math.min(cost1, Math.min(cost7, cost30));    }}

Complexity

Time

O(3^N), where N is the number of travel days. At each travel day, the function can branch into three recursive calls, leading to an exponential growth in the number of operations.

Space

O(N), where N is the number of travel days. This space is used by the recursion stack.

Trade-offs

Pros

  • Simple to conceptualize and implement directly from the problem statement.

Cons

  • Extremely inefficient due to a massive number of redundant calculations for the same subproblems.

  • Will result in a 'Time Limit Exceeded' (TLE) error for most inputs.

Solutions

class Solution {private  static final int[] T = new int[]{1, 7, 30};private  int[] costs;private  int[] days;private  int[] f;private  int n;public  int mincostTickets(int[] days, int[] costs) {    n = days.length;    f = new int[n];    this.costs = costs;    this.days = days;    Arrays.fill(f, -1);    return dfs(0);  }private  int dfs(int i) {    if (i >= n) {      return 0;    }    if (f[i] != -1) {      return f[i];    }    int res = Integer.MAX_VALUE;    for (int k = 0; k < 3; ++k) {      int j = lowerBound(days, days[i] + T[k]);      res = Math.min(res, costs[k] + dfs(j));    }    f[i] = res;    return res;  }private  int lowerBound(int[] days, int x) {    int left = 0, right = days.length;    while (left < right) {      int mid = (left + right) >> 1;      if (days[mid] >= x) {        right = mid;      } else {        left = mid + 1;      }    }    return left;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem