Minimum Cost for Tickets

🎯

Minimum Cost for Tickets

mediumDPAmazonGoogle

Imagine you are planning your travel days for the next few months and want to buy tickets that cover all your travel days at the minimum possible cost.

💡 This problem is a classic example of dynamic programming where you must minimize cost over a timeline with overlapping intervals. Beginners often struggle because the problem looks like a scheduling or greedy problem but requires considering all combinations of ticket purchases.

📋

Problem Statement

You are given an integer array days where each element is a day you will travel. You have tickets of three types: 1-day, 7-day, and 30-day passes with respective costs. Each pass covers consecutive days starting from the day of purchase. Return the minimum cost to cover all travel days.

1 ≤ days.length ≤ 10^51 ≤ days[i] ≤ 365days is strictly increasingcosts.length == 31 ≤ costs[i] ≤ 10^5

💡

Example

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

Output11

Buy 1-day pass on day 1 (cost 2), 7-day pass on day 4 (cost 7) covering days 4-10, and 1-day pass on day 20 (cost 2). Total = 11.

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

Output17

Buy 30-day pass on day 1 (cost 15) covering days 1-30, and 1-day pass on day 31 (cost 2). Total = 17.

• days = [1], costs = [2,7,15] → output: 2 (single day travel)
• days = [1,2,3,4,5,6,7], costs = [2,7,15] → output: 7 (7-day pass cheaper than multiple 1-day passes)
• days = [1,15,30], costs = [2,7,15] → output: 6 (three 1-day passes cheaper than longer passes)
• days = [1,2,3,4,5,6,7,8,9,10], costs = [10,2,1] → output: 10 (1-day passes expensive, 7-day pass very cheap)

🔁

Why DP?

Why greedy fails:

A greedy approach that always buys the cheapest ticket for the current day fails because buying a longer pass earlier might cover multiple days at a lower total cost. For example, if 1-day passes cost 2 and 7-day passes cost 7, buying seven 1-day passes costs 14, but one 7-day pass costs 7, which is cheaper.

DP state:

dp[i] represents the minimum cost to cover all travel days from the i-th travel day to the end.

Recurrence:dp[i] = min(costs[j] + dp[nextIndex]) for j in {0,1,2} where nextIndex is the first day index not covered by the j-th ticket starting at days[i]

For each ticket type, buy that ticket and add its cost to the minimum cost of covering the remaining days after the ticket expires; choose the minimum among these options.

⚠️

Common Mistakes

Not handling the base case correctly

Recursion or DP may access invalid indices causing errors or wrong answers

✅ Ensure dp[n] = 0 and recursion returns 0 when index >= n

Using linear search instead of binary search for next uncovered day in large inputs

Solution becomes too slow and may time out

✅ Use binary search to find next uncovered day efficiently

Forgetting to memoize recursive calls

Exponential time complexity and TLE

✅ Add memoization cache to store results of subproblems

Incorrectly calculating the next uncovered day index

May skip or double count days leading to wrong cost calculation

✅ Carefully find the first day not covered by the current ticket using correct comparison

Not considering all ticket types at each step

May miss cheaper options leading to suboptimal cost

✅ Always try all ticket types and pick minimum cost

🧠

Brute Force (Pure Recursion)

💡 Starting with brute force helps understand the problem's recursive structure and why naive solutions are inefficient due to repeated calculations.

Intuition

Try buying each ticket type at the current travel day and recursively compute the minimum cost for the remaining days not covered by that ticket.

Algorithm

1. Start from the first travel day index.
2. For each ticket type, find the next travel day index not covered by that ticket.
3. Recursively compute the cost for the remaining days starting from that next index.
4. Return the minimum total cost among all ticket options.

💡 The recursion explores all combinations, which is conceptually simple but computationally expensive.

Recurrence:dp(i) = min_{j in {1,7,30}} (cost_j + dp(nextIndex(i, j)))

</>

Code

def mincostTickets(days, costs):
    n = len(days)
    durations = [1,7,30]
    from functools import lru_cache

    @lru_cache(None)
    def dfs(i):
        if i >= n:
            return 0
        ans = float('inf')
        for j, d in enumerate(durations):
            cost = costs[j]
            next_i = i
            while next_i < n and days[next_i] < days[i] + d:
                next_i += 1
            ans = min(ans, cost + dfs(next_i))
        return ans

    return dfs(0)

# Example usage
if __name__ == '__main__':
    print(mincostTickets([1,4,6,7,8,20], [2,7,15]))  # Output: 11

Line Notes

def mincostTickets(days, costs):Defines main function to solve problem

durations = [1,7,30]Ticket durations corresponding to costs

@lru_cache(None)Memoizes dfs to avoid recomputation

if i >= n:Base case: no more days to cover

for j, d in enumerate(durations):Try each ticket type

while next_i < n and days[next_i] < days[i] + d:Find next day not covered by current ticket

ans = min(ans, cost + dfs(next_i))Choose minimum cost among ticket options

return dfs(0)Start recursion from first travel day

import java.util.*;

public class Solution {
    private int[] days, costs, durations = {1,7,30};
    private int n;
    private Map<Integer, Integer> memo = new HashMap<>();

    public int mincostTickets(int[] days, int[] costs) {
        this.days = days;
        this.costs = costs;
        this.n = days.length;
        return dfs(0);
    }

    private int dfs(int i) {
        if (i >= n) return 0;
        if (memo.containsKey(i)) return memo.get(i);
        int ans = Integer.MAX_VALUE;
        for (int j = 0; j < durations.length; j++) {
            int cost = costs[j];
            int d = durations[j];
            int next_i = i;
            while (next_i < n && days[next_i] < days[i] + d) next_i++;
            ans = Math.min(ans, cost + dfs(next_i));
        }
        memo.put(i, ans);
        return ans;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.mincostTickets(new int[]{1,4,6,7,8,20}, new int[]{2,7,15})); // 11
    }
}

Line Notes

private Map<Integer, Integer> memo = new HashMap<>();Memoization map to store results

if (i >= n) return 0;Base case: no more days to cover

while (next_i < n && days[next_i] < days[i] + d) next_i++;Find next uncovered day after ticket duration

ans = Math.min(ans, cost + dfs(next_i));Choose minimum cost among ticket options

memo.put(i, ans);Store computed result to avoid recomputation

return dfs(0);Start recursion from first travel day

#include <iostream>
#include <vector>
#include <unordered_map>
#include <climits>
using namespace std;

class Solution {
    vector<int> days, costs, durations = {1,7,30};
    int n;
    unordered_map<int,int> memo;
public:
    int dfs(int i) {
        if (i >= n) return 0;
        if (memo.count(i)) return memo[i];
        int ans = INT_MAX;
        for (int j = 0; j < 3; j++) {
            int cost = costs[j];
            int d = durations[j];
            int next_i = i;
            while (next_i < n && days[next_i] < days[i] + d) next_i++;
            ans = min(ans, cost + dfs(next_i));
        }
        return memo[i] = ans;
    }

    int mincostTickets(vector<int>& days_, vector<int>& costs_) {
        days = days_;
        costs = costs_;
        n = days.size();
        return dfs(0);
    }
};

int main() {
    Solution sol;
    vector<int> days = {1,4,6,7,8,20};
    vector<int> costs = {2,7,15};
    cout << sol.mincostTickets(days, costs) << endl; // 11
    return 0;
}

Line Notes

unordered_map<int,int> memo;Memoization map to cache results

if (i >= n) return 0;Base case: no more travel days

while (next_i < n && days[next_i] < days[i] + d) next_i++;Find next uncovered day after ticket duration

ans = min(ans, cost + dfs(next_i));Update minimum cost among ticket options

return memo[i] = ans;Store and return computed result

return dfs(0);Start recursion from first travel day

var mincostTickets = function(days, costs) {
    const durations = [1,7,30];
    const n = days.length;
    const memo = new Map();

    function dfs(i) {
        if (i >= n) return 0;
        if (memo.has(i)) return memo.get(i);
        let ans = Infinity;
        for (let j = 0; j < durations.length; j++) {
            let cost = costs[j];
            let d = durations[j];
            let next_i = i;
            while (next_i < n && days[next_i] < days[i] + d) next_i++;
            ans = Math.min(ans, cost + dfs(next_i));
        }
        memo.set(i, ans);
        return ans;
    }

    return dfs(0);
};

// Example usage
console.log(mincostTickets([1,4,6,7,8,20], [2,7,15])); // 11

Line Notes

const memo = new Map();Memoization map to cache results

if (i >= n) return 0;Base case: no more travel days

while (next_i < n && days[next_i] < days[i] + d) next_i++;Find next uncovered day after ticket duration

ans = Math.min(ans, cost + dfs(next_i));Update minimum cost among ticket options

memo.set(i, ans);Store computed result to avoid recomputation

return dfs(0);Start recursion from first travel day

⏱

Complexity

TimeO(n * 3 * n) = O(n^2) due to nested while loop inside recursion

SpaceO(n) for recursion stack and memoization

Each recursive call tries 3 ticket options and advances index by up to n, leading to quadratic complexity.

💡 For n=10, this means about 300 operations, but for n=10^5 it becomes infeasible.

Interview Verdict: TLE for large inputs, but useful to understand problem structure

Shows why naive recursion is too slow and motivates memoization and tabulation.

🧠

Top-Down DP with Memoization

💡 Memoization avoids recomputing states by caching results, drastically improving efficiency over brute force.

Intuition

Use recursion with caching to remember minimum costs for each starting day, avoiding repeated work.

Algorithm

1. Initialize a memo dictionary to store results for each index.
2. Recursively compute minimum cost starting from current index.
3. For each ticket type, find the next index after coverage ends.
4. Return and memoize the minimum cost among all ticket options.

💡 Memoization turns exponential recursion into polynomial time by caching.

Recurrence:dp(i) = min_{j in {1,7,30}} (cost_j + dp(nextIndex(i, j)))

</>

Code

def mincostTickets(days, costs):
    n = len(days)
    durations = [1,7,30]
    memo = {}

    def dfs(i):
        if i >= n:
            return 0
        if i in memo:
            return memo[i]
        ans = float('inf')
        for j, d in enumerate(durations):
            cost = costs[j]
            next_i = i
            while next_i < n and days[next_i] < days[i] + d:
                next_i += 1
            ans = min(ans, cost + dfs(next_i))
        memo[i] = ans
        return ans

    return dfs(0)

# Example usage
if __name__ == '__main__':
    print(mincostTickets([1,4,6,7,8,20], [2,7,15]))  # Output: 11

Line Notes

memo = {}Initialize cache for storing results

if i in memo:Return cached result if available

while next_i < n and days[next_i] < days[i] + d:Find next uncovered day after ticket duration

memo[i] = ansStore computed minimum cost for current index

return dfs(0)Start recursion from first travel day

import java.util.*;

public class Solution {
    private int[] days, costs, durations = {1,7,30};
    private int n;
    private Map<Integer, Integer> memo = new HashMap<>();

    public int mincostTickets(int[] days, int[] costs) {
        this.days = days;
        this.costs = costs;
        this.n = days.length;
        return dfs(0);
    }

    private int dfs(int i) {
        if (i >= n) return 0;
        if (memo.containsKey(i)) return memo.get(i);
        int ans = Integer.MAX_VALUE;
        for (int j = 0; j < durations.length; j++) {
            int cost = costs[j];
            int d = durations[j];
            int next_i = i;
            while (next_i < n && days[next_i] < days[i] + d) next_i++;
            ans = Math.min(ans, cost + dfs(next_i));
        }
        memo.put(i, ans);
        return ans;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.mincostTickets(new int[]{1,4,6,7,8,20}, new int[]{2,7,15})); // 11
    }
}

Line Notes

private Map<Integer, Integer> memo = new HashMap<>();Cache results to avoid recomputation

if (memo.containsKey(i)) return memo.get(i);Return cached result if available

while (next_i < n && days[next_i] < days[i] + d) next_i++;Find next uncovered day after ticket duration

memo.put(i, ans);Store computed minimum cost for current index

return dfs(0);Start recursion from first travel day

#include <iostream>
#include <vector>
#include <unordered_map>
#include <climits>
using namespace std;

class Solution {
    vector<int> days, costs, durations = {1,7,30};
    int n;
    unordered_map<int,int> memo;
public:
    int dfs(int i) {
        if (i >= n) return 0;
        if (memo.count(i)) return memo[i];
        int ans = INT_MAX;
        for (int j = 0; j < 3; j++) {
            int cost = costs[j];
            int d = durations[j];
            int next_i = i;
            while (next_i < n && days[next_i] < days[i] + d) next_i++;
            ans = min(ans, cost + dfs(next_i));
        }
        return memo[i] = ans;
    }

    int mincostTickets(vector<int>& days_, vector<int>& costs_) {
        days = days_;
        costs = costs_;
        n = days.size();
        return dfs(0);
    }
};

int main() {
    Solution sol;
    vector<int> days = {1,4,6,7,8,20};
    vector<int> costs = {2,7,15};
    cout << sol.mincostTickets(days, costs) << endl; // 11
    return 0;
}

Line Notes

unordered_map<int,int> memo;Cache results to avoid recomputation

if (memo.count(i)) return memo[i];Return cached result if available

while (next_i < n && days[next_i] < days[i] + d) next_i++;Find next uncovered day after ticket duration

return memo[i] = ans;Store computed minimum cost for current index

return dfs(0);Start recursion from first travel day

var mincostTickets = function(days, costs) {
    const durations = [1,7,30];
    const n = days.length;
    const memo = new Map();

    function dfs(i) {
        if (i >= n) return 0;
        if (memo.has(i)) return memo.get(i);
        let ans = Infinity;
        for (let j = 0; j < durations.length; j++) {
            let cost = costs[j];
            let d = durations[j];
            let next_i = i;
            while (next_i < n && days[next_i] < days[i] + d) next_i++;
            ans = Math.min(ans, cost + dfs(next_i));
        }
        memo.set(i, ans);
        return ans;
    }

    return dfs(0);
};

// Example usage
console.log(mincostTickets([1,4,6,7,8,20], [2,7,15])); // 11

Line Notes

const memo = new Map();Cache results to avoid recomputation

if (memo.has(i)) return memo.get(i);Return cached result if available

while (next_i < n && days[next_i] < days[i] + d) next_i++;Find next uncovered day after ticket duration

memo.set(i, ans);Store computed minimum cost for current index

return dfs(0);Start recursion from first travel day

⏱

Complexity

TimeO(n * 3 * log n) due to binary search optimization possible, else O(n^2)

SpaceO(n) for memo and recursion stack

Memoization reduces repeated calls, but searching next index can be optimized with binary search.

💡 For n=10^5, this approach is feasible with binary search; otherwise, it may be slow.

Interview Verdict: Accepted with memoization, but can be improved with tabulation and binary search

Memoization is a key step to optimize brute force and is often acceptable in interviews.

🧠

Bottom-Up DP (Tabulation)

💡 Tabulation builds the solution iteratively from the end, avoiding recursion overhead and making the process clearer and often faster.

Intuition

Start from the last travel day and compute minimum cost backward, using previously computed results for future days.

Algorithm

1. Initialize dp array of size n+1 with dp[n] = 0 (no cost after last day).
2. Iterate i from n-1 down to 0.
3. For each ticket type, find next index after coverage ends.
4. Set dp[i] as minimum of cost of ticket plus dp[nextIndex].

💡 This approach ensures all needed subproblems are solved before current one.

Recurrence:dp[i] = min_{j in {1,7,30}} (costs[j] + dp[nextIndex(i, j)])

</>

Code

def mincostTickets(days, costs):
    n = len(days)
    durations = [1,7,30]
    dp = [0] * (n + 1)

    for i in range(n - 1, -1, -1):
        ans = float('inf')
        for j, d in enumerate(durations):
            cost = costs[j]
            next_i = i
            while next_i < n and days[next_i] < days[i] + d:
                next_i += 1
            ans = min(ans, cost + dp[next_i])
        dp[i] = ans

    return dp[0]

# Example usage
if __name__ == '__main__':
    print(mincostTickets([1,4,6,7,8,20], [2,7,15]))  # Output: 11

Line Notes

dp = [0] * (n + 1)Initialize dp array with base case dp[n] = 0

for i in range(n - 1, -1, -1):Fill dp from last day backward

while next_i < n and days[next_i] < days[i] + d:Find next uncovered day after ticket duration

ans = min(ans, cost + dp[next_i])Choose minimum cost among ticket options

dp[i] = ansStore minimum cost for current index

import java.util.*;

public class Solution {
    public int mincostTickets(int[] days, int[] costs) {
        int n = days.length;
        int[] durations = {1,7,30};
        int[] dp = new int[n + 1];

        for (int i = n - 1; i >= 0; i--) {
            int ans = Integer.MAX_VALUE;
            for (int j = 0; j < durations.length; j++) {
                int cost = costs[j];
                int d = durations[j];
                int next_i = i;
                while (next_i < n && days[next_i] < days[i] + d) next_i++;
                ans = Math.min(ans, cost + dp[next_i]);
            }
            dp[i] = ans;
        }

        return dp[0];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.mincostTickets(new int[]{1,4,6,7,8,20}, new int[]{2,7,15})); // 11
    }
}

Line Notes

int[] dp = new int[n + 1];Initialize dp array with base case dp[n] = 0

for (int i = n - 1; i >= 0; i--)Fill dp from last day backward

while (next_i < n && days[next_i] < days[i] + d) next_i++;Find next uncovered day after ticket duration

ans = Math.min(ans, cost + dp[next_i]);Choose minimum cost among ticket options

dp[i] = ans;Store minimum cost for current index

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        int n = days.size();
        vector<int> durations = {1,7,30};
        vector<int> dp(n + 1, 0);

        for (int i = n - 1; i >= 0; i--) {
            int ans = INT_MAX;
            for (int j = 0; j < 3; j++) {
                int cost = costs[j];
                int d = durations[j];
                int next_i = i;
                while (next_i < n && days[next_i] < days[i] + d) next_i++;
                ans = min(ans, cost + dp[next_i]);
            }
            dp[i] = ans;
        }

        return dp[0];
    }
};

int main() {
    Solution sol;
    vector<int> days = {1,4,6,7,8,20};
    vector<int> costs = {2,7,15};
    cout << sol.mincostTickets(days, costs) << endl; // 11
    return 0;
}

Line Notes

vector<int> dp(n + 1, 0);Initialize dp array with base case dp[n] = 0

for (int i = n - 1; i >= 0; i--)Fill dp from last day backward

while (next_i < n && days[next_i] < days[i] + d) next_i++;Find next uncovered day after ticket duration

ans = min(ans, cost + dp[next_i]);Choose minimum cost among ticket options

dp[i] = ans;Store minimum cost for current index

var mincostTickets = function(days, costs) {
    const durations = [1,7,30];
    const n = days.length;
    const dp = new Array(n + 1).fill(0);

    for (let i = n - 1; i >= 0; i--) {
        let ans = Infinity;
        for (let j = 0; j < durations.length; j++) {
            let cost = costs[j];
            let d = durations[j];
            let next_i = i;
            while (next_i < n && days[next_i] < days[i] + d) next_i++;
            ans = Math.min(ans, cost + dp[next_i]);
        }
        dp[i] = ans;
    }

    return dp[0];
};

// Example usage
console.log(mincostTickets([1,4,6,7,8,20], [2,7,15])); // 11

Line Notes

const dp = new Array(n + 1).fill(0);Initialize dp array with base case dp[n] = 0

for (let i = n - 1; i >= 0; i--)Fill dp from last day backward

while (next_i < n && days[next_i] < days[i] + d) next_i++;Find next uncovered day after ticket duration

ans = Math.min(ans, cost + dp[next_i]);Choose minimum cost among ticket options

dp[i] = ans;Store minimum cost for current index

⏱

Complexity

TimeO(n * 3 * n) = O(n^2) due to nested while loop

SpaceO(n) for dp array

Each dp[i] requires scanning forward to find next uncovered day, leading to quadratic time.

💡 For large n, this can be optimized using binary search to find next_i.

Interview Verdict: Accepted, but can be optimized further with binary search and space optimization

Tabulation is preferred over recursion in interviews for clarity and performance.

🧠

Bottom-Up DP with Binary Search Optimization

💡 Using binary search to find the next uncovered day reduces the inner loop from O(n) to O(log n), improving time complexity significantly.

Intuition

Instead of scanning linearly to find the next uncovered day, use binary search on the sorted days array.

Algorithm

1. Precompute dp array with dp[n] = 0.
2. For each day from last to first, use binary search to find next uncovered day for each ticket.
3. Calculate minimum cost among all ticket options plus dp of next uncovered day.
4. Store result in dp[i].

💡 Binary search reduces the time to find next uncovered day, making the solution scalable.

Recurrence:dp[i] = min_{j in {1,7,30}} (costs[j] + dp[nextIndex(i, j)]) with nextIndex found by binary search

</>

Code

import bisect

def mincostTickets(days, costs):
    n = len(days)
    durations = [1,7,30]
    dp = [0] * (n + 1)

    for i in range(n - 1, -1, -1):
        ans = float('inf')
        for j, d in enumerate(durations):
            cost = costs[j]
            next_day = days[i] + d
            next_i = bisect.bisect_left(days, next_day, i, n)
            ans = min(ans, cost + dp[next_i])
        dp[i] = ans

    return dp[0]

# Example usage
if __name__ == '__main__':
    print(mincostTickets([1,4,6,7,8,20], [2,7,15]))  # Output: 11

Line Notes

import bisectImport binary search module

next_i = bisect.bisect_left(days, next_day, i, n)Find next uncovered day index efficiently

dp = [0] * (n + 1)Initialize dp array with base case

for i in range(n - 1, -1, -1):Fill dp backward

dp[i] = ansStore minimum cost for current index

import java.util.*;

public class Solution {
    public int mincostTickets(int[] days, int[] costs) {
        int n = days.length;
        int[] durations = {1,7,30};
        int[] dp = new int[n + 1];

        for (int i = n - 1; i >= 0; i--) {
            int ans = Integer.MAX_VALUE;
            for (int j = 0; j < durations.length; j++) {
                int cost = costs[j];
                int d = durations[j];
                int next_i = binarySearch(days, days[i] + d, i, n);
                ans = Math.min(ans, cost + dp[next_i]);
            }
            dp[i] = ans;
        }

        return dp[0];
    }

    private int binarySearch(int[] days, int target, int left, int right) {
        int l = left, r = right;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (days[mid] >= target) r = mid;
            else l = mid + 1;
        }
        return l;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.mincostTickets(new int[]{1,4,6,7,8,20}, new int[]{2,7,15})); // 11
    }
}

Line Notes

private int binarySearch(int[] days, int target, int left, int right)Binary search to find next uncovered day index

int l = left, r = right;Initialize binary search boundaries

if (days[mid] >= target) r = mid; else l = mid + 1;Adjust search space based on comparison

dp[i] = ans;Store minimum cost for current index

return dp[0];Return minimum cost starting from first travel day

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

class Solution {
public:
    int binarySearch(const vector<int>& days, int target, int left, int right) {
        int l = left, r = right;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (days[mid] >= target) r = mid;
            else l = mid + 1;
        }
        return l;
    }

    int mincostTickets(vector<int>& days, vector<int>& costs) {
        int n = days.size();
        vector<int> durations = {1,7,30};
        vector<int> dp(n + 1, 0);

        for (int i = n - 1; i >= 0; i--) {
            int ans = INT_MAX;
            for (int j = 0; j < 3; j++) {
                int cost = costs[j];
                int d = durations[j];
                int next_i = binarySearch(days, days[i] + d, i, n);
                ans = min(ans, cost + dp[next_i]);
            }
            dp[i] = ans;
        }

        return dp[0];
    }
};

int main() {
    Solution sol;
    vector<int> days = {1,4,6,7,8,20};
    vector<int> costs = {2,7,15};
    cout << sol.mincostTickets(days, costs) << endl; // 11
    return 0;
}

Line Notes

int binarySearch(const vector<int>& days, int target, int left, int right)Binary search to find next uncovered day index

if (days[mid] >= target) r = mid; else l = mid + 1;Adjust search space based on comparison

dp[i] = ans;Store minimum cost for current index

return dp[0];Return minimum cost starting from first travel day

vector<int> dp(n + 1, 0);Initialize dp array with base case

var mincostTickets = function(days, costs) {
    const durations = [1,7,30];
    const n = days.length;
    const dp = new Array(n + 1).fill(0);

    function binarySearch(target, left, right) {
        let l = left, r = right;
        while (l < r) {
            let mid = Math.floor((l + r) / 2);
            if (days[mid] >= target) r = mid;
            else l = mid + 1;
        }
        return l;
    }

    for (let i = n - 1; i >= 0; i--) {
        let ans = Infinity;
        for (let j = 0; j < durations.length; j++) {
            let cost = costs[j];
            let d = durations[j];
            let next_i = binarySearch(days[i] + d, i, n);
            ans = Math.min(ans, cost + dp[next_i]);
        }
        dp[i] = ans;
    }

    return dp[0];
};

// Example usage
console.log(mincostTickets([1,4,6,7,8,20], [2,7,15])); // 11

Line Notes

function binarySearch(target, left, right)Binary search to find next uncovered day index

if (days[mid] >= target) r = mid; else l = mid + 1;Adjust search space based on comparison

dp[i] = ans;Store minimum cost for current index

return dp[0];Return minimum cost starting from first travel day

const dp = new Array(n + 1).fill(0);Initialize dp array with base case

⏱

Complexity

TimeO(n * 3 * log n) = O(n log n)

SpaceO(n) for dp array

Binary search reduces the inner loop from O(n) to O(log n), making the solution efficient for large inputs.

💡 For n=10^5, this approach is practical and efficient.

Interview Verdict: Accepted and optimal for large inputs

This is the recommended approach in interviews for this problem.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, start with brute force to explain the problem, then implement memoization or bottom-up DP with binary search for optimal performance.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(3^n) exponential	O(n) recursion stack	Yes (deep recursion)	No	Mention only - never code
2. Top-Down DP with Memoization	O(n^2) or O(n log n) with binary search	O(n) memo + recursion stack	Possible but less likely	Yes	Good for initial optimization
3. Bottom-Up DP (Tabulation)	O(n^2) without binary search	O(n)	No	Yes	Preferred for clarity and performance
4. Bottom-Up DP with Binary Search	O(n log n)	O(n)	No	Yes	Optimal solution to implement

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and know when and how to optimize your solution during interviews.

How to Present

Clarify the problem and constraints.Explain the brute force recursive approach to show understanding.Introduce memoization to optimize recursion.Present bottom-up DP for clarity and efficiency.Optimize with binary search for large inputs.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

Understanding of DP concepts, ability to optimize naive solutions, and knowledge of binary search for efficiency.

Common Follow-ups

• What if ticket durations or costs change dynamically? → Use segment trees or advanced data structures.
• Can we reconstruct which tickets were bought? → Yes, by storing choices during DP.

💡 These follow-ups test deeper understanding and ability to extend solutions.

🔍

Pattern Recognition

When to Use

1) Problem involves covering intervals or days with tickets or passes; 2) Costs are associated with different durations; 3) Need to minimize total cost; 4) Overlapping intervals suggest DP.

Signature Phrases

'minimum cost to cover all travel days''tickets with different durations and costs'

NOT This Pattern When

Problems that require greedy interval scheduling without overlapping or fixed intervals.

Similar Problems

Coin Change II - similar unbounded knapsack with counting waysPaint House - scheduling with cost minimizationJump Game VI - minimum cost path with constraints

Practice

1. You are given a set of items, each with a weight and a value, and a knapsack with a maximum weight capacity. You want to maximize the total value of items placed in the knapsack without exceeding its capacity. Which algorithmic approach guarantees finding the optimal solution for this problem?

easy

A. A greedy algorithm that picks items with the highest value-to-weight ratio first.

B. Dynamic programming that considers including or excluding each item for every capacity up to the maximum.

C. A simple recursive approach without memoization that tries all subsets of items.

D. A breadth-first search exploring all possible combinations of items.

Solution

1. Step 1: Understand problem constraints and overlapping subproblems

   The problem requires maximizing value without exceeding capacity, which is a classic optimization problem with overlapping subproblems suitable for dynamic programming.

2. Step 2: Identify algorithmic approach that guarantees optimality

   Greedy algorithms fail because picking locally optimal items (highest value/weight) does not guarantee global optimum. Exhaustive search is correct but inefficient. Dynamic programming systematically explores all item inclusion/exclusion states with memoization, ensuring optimality.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DP solves 0/1 Knapsack optimally by exploring all states [OK]

Hint: DP with inclusion/exclusion ensures optimal solution [OK]

Common Mistakes:

• Greedy approach works for fractional knapsack, not 0/1 knapsack.

2. Consider the following code snippet for the coin change problem. What is the value of dp[5] after the outer loop iteration i=5 completes when coins = [1, 2, 5] and amount = 5?

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], 1 + dp[i - coin])
    return dp[amount]

print(coinChange([1,2,5], 5))

easy

A. 5

B. 2

C. 3

D. 1

Solution

1. Step 1: Trace dp array updates up to i=5

   dp[0]=0; For i=1: dp[1]=min(inf,1+dp[0])=1; i=2: dp[2]=min(inf,1+dp[1],1+dp[0])=1; i=3: dp[3]=min(inf,1+dp[2],1+dp[1])=2; i=4: dp[4]=min(inf,1+dp[3],1+dp[2])=2; i=5: dp[5]=min(inf,1+dp[4],1+dp[3],1+dp[0])=min(inf,3,3,1)=1

2. Step 2: Confirm dp[5] value

   Using coin 5 directly gives dp[5]=1, which is minimal.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   dp[5] = 1 coin (coin 5) [OK]

Hint: Direct coin equal to amount sets dp[amount] to 1 [OK]

Common Mistakes:

• Off-by-one errors in indexing dp
• Ignoring direct coin match

3. You are given a list of positive integers and need to determine if it can be split into two subsets with equal sums. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Dynamic programming using a subset-sum style 0/1 knapsack approach to check for a subset with sum equal to half the total

B. Divide and conquer by recursively splitting the array into halves and checking sums

C. Sorting the array and using two pointers to find two subsets with equal sums

D. Greedy algorithm that picks the largest elements first until half the total sum is reached

Solution

1. Step 1: Understand the problem requires partitioning into two equal sum subsets

   Since the problem asks if the array can be split into two subsets with equal sums, it reduces to finding a subset with sum equal to half the total sum.

2. Step 2: Identify the algorithm that checks subset sums efficiently

   The 0/1 knapsack dynamic programming approach can determine if such a subset exists by building a DP table or array that tracks achievable sums up to half the total.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Greedy and sorting approaches fail on many inputs; DP guarantees correctness [OK]

Hint: Partition reduces to subset sum with half total [OK]

Common Mistakes:

• Thinking greedy or sorting solves partition optimally

4. You are given a set of stones with positive integer weights. You want to split them into two groups such that the difference between the sum of weights in the two groups is minimized. Which algorithmic approach guarantees finding the minimal possible difference?

easy

A. A dynamic programming approach similar to 0/1 knapsack that finds achievable sums up to half the total weight

B. A breadth-first search exploring all subsets of stones without pruning

C. A greedy algorithm that repeatedly smashes the two heaviest stones until one or none remain

D. A divide-and-conquer approach that recursively splits stones into halves and merges results

Solution

1. Step 1: Understand the problem as partitioning stones into two subsets with minimal difference

   This is a classic subset-sum variation where we want to find a subset with sum as close as possible to half the total.

2. Step 2: Recognize that 0/1 knapsack DP can find achievable sums up to half total weight

   By using DP to track which sums are possible, we can find the closest sum to half, minimizing the difference.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Greedy fails on some inputs; DP guarantees minimal difference [OK]

Hint: Minimal difference -> subset sum DP, not greedy [OK]

Common Mistakes:

• Believing greedy smashing always yields minimal difference
• Thinking divide-and-conquer without DP suffices
• Assuming BFS is efficient enough here

5. Suppose the subset sum problem is modified so that each number can be chosen multiple times (unbounded). Which modification to the space-optimized DP code correctly solves this variant?

hard

A. Change the inner loop to iterate forwards from num to S, allowing reuse of the same number multiple times.

B. Keep the inner loop iterating backwards from S to num, as in the 0/1 subset sum problem.

C. Use a recursive brute force approach without memoization to handle multiple uses.

D. Sort the input array and apply a greedy approach picking largest numbers first.

Solution

1. Step 1: Understand difference between 0/1 and unbounded knapsack

   In unbounded knapsack, items can be reused multiple times, so dp updates must allow reuse within the same iteration.

2. Step 2: Modify iteration direction

   Iterating forwards allows dp[w] to use dp[w - num] updated in the same iteration, enabling multiple uses of num.

3. Step 3: Confirm correctness

   Backward iteration prevents reuse in the same iteration, which is incorrect for unbounded variant.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Forward iteration enables multiple uses -> correct for unbounded knapsack [OK]

Hint: Unbounded knapsack requires forward iteration to allow reuse [OK]

Common Mistakes:

• Using backward iteration from 0/1 knapsack
• Trying greedy or brute force without memoization