Minimum Cost For Tickets Leetcode Solution

Difficulty Level Medium
Frequently asked in Adobe Amazon Apple Bloomberg Facebook Goldman Sachs Google
Array Dynamic Programming ShopeeViews 5921

Problem Statement

The Minimum Cost For Tickets LeetCode Solution – “Minimum Cost For Tickets” asks you to find the minimum number of dollars you need to travel every day in the given list of days.

You will be given an integer array of days. Each day is an integer from 1 to 365. Tickets are sold in the following 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.

Example:

Input:  days = [1,4,6,7,8,20], costs = [2,7,15]
Output: 11

Explanation:

  • One of the ways that minimize the overall cost are:- [1,1], [3,7], [20,1].
  • [a,b] denotes buying pass b on day number a.
Input:  days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
Output: 17

Explanation:

  • One of the ways that minimize the overall cost is:- [1,30], [31,1].
  • [a,b] denotes buying pass b on day number a.

Approach

Idea:

  1. The main idea to solve this problem is to use dynamic programming.
  2. Let dp[i] means the minimum cost of tickets up to the day i.
  3. The size of the DP array depends on the last travel day, so we don’t need an array length to be 365.
  4. We do need a boolean array to mark the travel days, the reason is if it is not a travel day we don’t need a ticket. However, if it is a travel day, we consider three scenarios (with three types of tickets):
    1. dp[i] = dp[i-1] + costs[0] for 1 day pass.
    2. dp[i] = dp[max(i-7,0)] + costs[1] for 7 day pass.
    3. As 30 days pass, dp[i] = dp[max(i-30,0)] + costs[2].
  5. Our answer will be a minimum of all the above DP values ending on the Last Day.

Code

Minimum Cost For Tickets Leetcode C++ Solution:

class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        int n = days.size(),lastDay = days.back();
        vector<int> dp(lastDay+1),isTravelDays(lastDay+1);
        for(auto& day:days){
            isTravelDays[day] = true;
        }
        for(int i=1;i<=lastDay;i++){
            if(!isTravelDays[i]){
                dp[i] = dp[i-1];
                continue;
            }
            dp[i] = dp[i-1] + costs[0];
            dp[i] = min(dp[i],dp[max(i-7,0)]+costs[1]);
            dp[i] = min(dp[i],dp[max(i-30,0)]+costs[2]);
        }
        return dp.back();
    }
};

Minimum Cost For Tickets Leetcode Java Solution:

class Solution {
    public int mincostTickets(int[] days, int[] costs) {
        int lastDay = days[days.length - 1]; 
        int[] dp = new int[lastDay + 1]; 
        boolean[] isTravelDays = new boolean[lastDay + 1];
        for(int day : days){
            isTravelDays[day] = true;
        }
        for(int i = 1; i <= lastDay; i++) {
            if(!isTravelDays[i]) {
                dp[i] = dp[i - 1];
                continue;
            }
            dp[i] =costs[0] + dp[i - 1];
            dp[i] = Math.min(costs[1] + dp[Math.max(i - 7, 0)], dp[i]);
            dp[i] = Math.min(costs[2] + dp[Math.max(i - 30, 0)], dp[i]);
        }
        return dp[lastDay];
    }
}

Complexity Analysis for Minimum Cost For Tickets Leetcode Solution

Time Complexity

The time complexity of the above code is O(last Day) since we traversed the linear dynamic programming vector exactly last day times.

Space Complexity

The space complexity of the above code is O(last day). A linear array is used to store the intermediate values.

Reference: https://en.wikipedia.org/wiki/Dynamic_programming

Translate »