Minimum Cost For Tickets - Practice Coding Problems

Minimum Cost For Tickets - Problem

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
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.

Input & Output

Example 1 — Basic Case

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

› Output: 11

💡 Note: Buy 7-day pass on day 1 covering days 1,4,6,7,8 ($7) + 1-day pass on day 20 ($2) = $9. Wait, let me recalculate: 7-day pass covers 7 consecutive days from purchase. Day 1 pass covers days 1-7, so covers days 1,4,6,7. Day 8 needs separate pass. Better: 1-day passes for days 1,4,6 ($6) + 7-day pass on day 7 covers days 7,8 ($7) + 1-day pass day 20 ($2) = $15. Actually optimal: 7-day pass on day 1 covers days 1-7 ($7) + 1-day pass day 8 ($2) + 1-day pass day 20 ($2) = $11

Example 2 — 30-day Pass Optimal

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

› Output: 17

💡 Note: 30-day pass on day 1 covers days 1-30 ($15) + 1-day pass on day 31 ($2) = $17. This beats buying multiple 7-day passes.

Example 3 — Sparse Travel Days

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

› Output: 6

💡 Note: When 7-day pass costs less than 1-day pass: 7-day pass on day 1 covers days 1-7 ($2) + 7-day pass on day 20 covers day 20 ($2) + 7-day pass on day 8 covers day 8 ($2) = $6

Constraints

1 ≤ days.length ≤ 365
1 ≤ days[i] ≤ 365
days is in strictly increasing order
costs.length == 3
1 ≤ costs[i] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Travel days [1,4,6,7,8,20] and costs [2,7,15] for 1/7/30-day passes

Process

For each day, choose cheapest pass option that covers it

Output

Minimum total cost $11

Key Takeaway

🎯 Key Insight: Use dynamic programming to choose the optimal pass for each day by comparing all three options and their future costs

Asked in

G Google 25 f Facebook 20 a Amazon 18 🍎 Apple 15

The key insight is that for each travel day, we need to choose the most cost-effective pass option. The optimal approach uses dynamic programming to build up the minimum cost by working backwards from the last travel day. For each day, we compare: 1-day pass + cost for remaining days, 7-day pass + cost after 7 days, and 30-day pass + cost after 30 days. Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Bottom-Up Dynamic Programming	O(n)	O(n)	Build solution iteratively from the end using DP array
Recursive Brute Force	O(3ⁿ)	O(n)	Try all possible combinations of passes recursively
Top-Down Dynamic Programming (Memoization)	O(n)	O(n)	Cache recursive results to avoid repeated calculations

Bottom-Up Dynamic Programming — Algorithm Steps

Create DP array indexed by day positions
Start from the last travel day
For each day, calculate min cost of 1-day, 7-day, 30-day passes
Use previously computed values for future days

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Create DP array with base case dp[n] = 0

Fill Table

Work backwards, computing minimum cost for each position

Result

dp[0] contains the minimum cost for all days

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* days, int daysSize, int* costs) {
    int* dp = (int*)calloc(daysSize + 1, sizeof(int)); // dp[i] = min cost from day i onwards
    
    // Work backwards from last day
    for (int i = daysSize - 1; i >= 0; i--) {
        // Option 1: Buy 1-day pass
        int cost1 = costs[0] + dp[i + 1];
        
        // Option 2: Buy 7-day pass
        int j = i;
        while (j < daysSize && days[j] < days[i] + 7) {
            j++;
        }
        int cost7 = costs[1] + dp[j];
        
        // Option 3: Buy 30-day pass
        int k = i;
        while (k < daysSize && days[k] < days[i] + 30) {
            k++;
        }
        int cost30 = costs[2] + dp[k];
        
        int min_val = cost1;
        if (cost7 < min_val) min_val = cost7;
        if (cost30 < min_val) min_val = cost30;
        dp[i] = min_val;
    }
    
    int result = dp[0];
    free(dp);
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int days[365], daysSize = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        days[daysSize++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    fgets(line, sizeof(line), stdin);
    int costs[3], costsSize = 0;
    token = strtok(line, "[],\n");
    while (token != NULL) {
        costs[costsSize++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    printf("%d\n", solution(days, daysSize, costs));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through n travel days, constant work per day

✓ Linear Growth

Space Complexity

O(n)

DP array stores minimum cost for each of n travel day positions

⚡ Linearithmic Space

185.4K Views

Medium Frequency

~25 min Avg. Time

3.4K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Bottom-Up Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler