Bird
Raised Fist0
Interview Prepdp-knapsackmediumAmazonGoogle

Minimum Cost for Tickets

Choose your preparation mode4 modes available
🎯
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.
ApproachTimeSpaceStack RiskReconstructUse In Interview
1. Brute ForceO(3^n) exponentialO(n) recursion stackYes (deep recursion)NoMention only - never code
2. Top-Down DP with MemoizationO(n^2) or O(n log n) with binary searchO(n) memo + recursion stackPossible but less likelyYesGood for initial optimization
3. Bottom-Up DP (Tabulation)O(n^2) without binary searchO(n)NoYesPreferred for clarity and performance
4. Bottom-Up DP with Binary SearchO(n log n)O(n)NoYesOptimal 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/5)
1. Consider the following Python code for the Equal Partition problem. What is the value of dp[target] after processing the input [1, 5, 11, 5]?
def canPartition(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True

    for num in nums:
        for w in range(target, num - 1, -1):
            dp[w] = dp[w] or dp[w - num]

    return dp[target]

print(canPartition([1,5,11,5]))
easy
A. true
B. false
C. null (error occurs)
D. Depends on order of iteration

Solution

  1. Step 1: Calculate total and target

    The total sum is 1 + 5 + 11 + 5 = 22, which is even, so target = 11.
  2. Step 2: Trace dp array updates for each num

    After processing all nums, dp[11] becomes True because subset {11} or {5,5,1} sums to 11.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Input is classic example where partition exists; dp[target] is True [OK]
Hint: Sum is even and dp[target] tracks subset sums [OK]
Common Mistakes:
  • Confusing dp[target] with dp[target-1]
  • Forgetting to iterate backwards in dp update
2. You need to split a positive integer n into at least two positive integers such that the product of these integers is maximized. Which algorithmic approach guarantees finding the optimal solution efficiently?
easy
A. Pure brute force recursion exploring all partitions without memoization
B. A greedy approach that always cuts the integer into 3s and 2s
C. Dynamic programming using bottom-up tabulation with state representing maximum product for each integer up to n
D. Divide and conquer by splitting the integer into two halves recursively without caching results

Solution

  1. Step 1: Understand problem structure

    The problem requires maximizing product by splitting an integer into parts, which naturally fits a DP approach where subproblems represent maximum product for smaller integers.
  2. Step 2: Evaluate options

    Greedy (always cutting 3s) fails on some inputs; brute force recursion is correct but inefficient; divide and conquer without memoization repeats work. Bottom-up DP tabulation efficiently computes all subproblems and combines results.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    DP tabulation ensures optimal substructure and overlapping subproblems [OK]
Hint: DP tabulation handles overlapping subproblems optimally [OK]
Common Mistakes:
  • Believing greedy always works for integer break
  • Ignoring memoization in recursion
3. What is the time complexity of the optimal job scheduling algorithm that sorts jobs by end time and uses binary search with a DP array of size n?
medium
A. O(n log W) where W is the maximum end time
B. O(n^2) due to nested loops over all jobs
C. O(n) because each job is processed once
D. O(n log n) due to sorting and binary searches for each job

Solution

  1. Step 1: Identify sorting cost

    Sorting n jobs by end time costs O(n log n).
  2. Step 2: Analyze DP loop with binary search

    For each job, binary search among ends array costs O(log n), repeated n times -> O(n log n).
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Sorting + n binary searches dominate; no nested O(n^2) loops [OK]
Hint: Sorting + binary search per job -> O(n log n) [OK]
Common Mistakes:
  • Assuming O(n^2) due to DP
  • Ignoring binary search cost
  • Confusing max end time W with input size n
4. Suppose the stones can be used multiple times (unlimited quantity of each stone). Which modification to the DP approach correctly computes the minimal last stone weight?
hard
A. Use a greedy approach smashing largest stones repeatedly
B. Keep the inner loop iterating backwards as in 0/1 knapsack to avoid reuse
C. Change the inner loop to iterate forwards from weight to half, allowing reuse of stones
D. Use recursion without memoization to explore all combinations with reuse

Solution

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

    For unlimited reuse, inner loop must iterate forwards to allow multiple counts of the same stone.
  2. Step 2: Modify DP accordingly

    Iterating forwards from weight to half updates dp[w] using dp[w - weight] from the same iteration, enabling reuse.
  3. Step 3: Why other options fail

    Backward iteration prevents reuse; greedy is incorrect; recursion without memoization is inefficient.
  4. Final Answer:

    Option C -> Option C
  5. Quick Check:

    Forward iteration in inner loop enables unlimited stone reuse [OK]
Hint: Unbounded knapsack -> inner loop forwards [OK]
Common Mistakes:
  • Using backward iteration causing no reuse
  • Trying greedy which is incorrect
  • Ignoring memoization leading to TLE
5. Suppose the Target Sum problem is modified so that each number in the array can be used multiple times (unlimited reuse). Which of the following changes correctly adapts the DP solution to this variant?
hard
A. Use a 1D dp array and update dp in forward order for each num to allow reuse
B. Keep the same DP with offset and update dp in reverse order to avoid double counting
C. Use a 2D dp array with dimensions n and sum, but only update dp[i][s] from dp[i-1][s-num]
D. Switch to a brute force recursion since DP cannot handle reuse

Solution

  1. Step 1: Understand reuse impact on DP iteration

    Allowing unlimited reuse means for each num, dp must be updated in forward order so that dp[s-num] includes ways using current num multiple times.
  2. Step 2: Identify correct DP update order

    Backward iteration prevents reuse by only using previous states. Forward iteration accumulates counts correctly for unlimited usage.
  3. Step 3: Evaluate options

    Use a 1D dp array and update dp in forward order for each num to allow reuse correctly updates dp forward. Keep the same DP with offset and update dp in reverse order to avoid double counting backward iteration is for no reuse. Use a 2D dp array with dimensions n and sum, but only update dp[i][s] from dp[i-1][s-num] restricts to previous items only. Switch to a brute force recursion since DP cannot handle reuse is inefficient.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Forward dp update enables multiple usage of same number [OK]
Hint: Forward dp iteration enables unlimited reuse [OK]
Common Mistakes:
  • Using backward iteration which forbids reuse
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard