Skip to content

983. Minimum Cost For Tickets 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  int mincostTickets(vector<int>& days, vector<int>& costs) {
    int ans = 0;
    queue<pair<int, int>> last7;
    queue<pair<int, int>> last30;

    for (const int day : days) {
      while (!last7.empty() && last7.front().first + 7 <= day)
        last7.pop();
      while (!last30.empty() && last30.front().first + 30 <= day)
        last30.pop();
      last7.emplace(day, ans + costs[1]);
      last30.emplace(day, ans + costs[2]);
      ans = min({ans + costs[0], last7.front().second, last30.front().second});
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public int mincostTickets(int[] days, int[] costs) {
    int ans = 0;
    Queue<Pair<Integer, Integer>> last7 = new ArrayDeque<>(); // [day, cost]
    Queue<Pair<Integer, Integer>> last30 = new ArrayDeque<>();

    for (final int day : days) {
      while (!last7.isEmpty() && last7.peek().getKey() + 7 <= day)
        last7.poll();
      while (!last30.isEmpty() && last30.peek().getKey() + 30 <= day)
        last30.poll();
      last7.offer(new Pair<>(day, ans + costs[1]));
      last30.offer(new Pair<>(day, ans + costs[2]));
      ans = Math.min(ans + costs[0], Math.min(last7.peek().getValue(), last30.peek().getValue()));
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def mincostTickets(self, days: list[int], costs: list[int]) -> int:
    ans = 0
    last7 = collections.deque()
    last30 = collections.deque()

    for day in days:
      while last7 and last7[0][0] + 7 <= day:
        last7.popleft()
      while last30 and last30[0][0] + 30 <= day:
        last30.popleft()
      last7.append([day, ans + costs[1]])
      last30.append([day, ans + costs[2]])
      ans = min(ans + costs[0], last7[0][1], last30[0][1])

    return ans