Coin Change II (Count Ways)

🎯

Coin Change II (Count Ways)

mediumDPAmazonGoogle

Imagine you have an unlimited supply of different coin denominations and want to find out how many distinct ways you can make a certain amount. This problem models that real-world scenario of counting combinations.

💡 This is a classic dynamic programming problem where beginners often struggle to understand why greedy approaches fail and how to count combinations without double counting. The challenge is to systematically explore all possibilities efficiently.

📋

Problem Statement

Given an integer amount and a list of distinct coin denominations, return the number of combinations that make up that amount. You may use an unlimited number of coins of each denomination. The order of coins does not matter.

1 ≤ amount ≤ 10^51 ≤ number of coins ≤ 3001 ≤ coin denomination ≤ 10^4

💡

Example

Input"amount = 5, coins = [1, 2, 5]"

Output4

The four combinations are: 5=5; 5=2+2+1; 5=2+1+1+1; 5=1+1+1+1+1

• amount = 0, coins = [1, 2] → 1 (empty combination)
• amount = 3, coins = [] → 0 (no coins to form amount)
• amount = 10, coins = [10] → 1 (only one coin equals amount)
• amount = 7, coins = [2, 4] → 0 (no combination possible)

🔁

Why DP?

Why greedy fails:

Greedy fails because choosing the largest coin first does not guarantee all combinations are counted. For example, amount=5 with coins=[1,2,5]: greedy picks 5 once, but misses combinations like 2+2+1.

DP state:

dp[i][w] represents the number of ways to make amount w using the first i types of coins.

Recurrence:dp[i][w] = dp[i-1][w] + dp[i][w - coins[i-1]] if w >= coins[i-1], else dp[i-1][w]

Number of ways to make w using first i coins = ways without current coin + ways including current coin (if possible).

⚠️

Common Mistakes

Using greedy approach

Misses valid combinations, returns incorrect count

✅ Use DP to count all combinations systematically

Counting permutations instead of combinations

Overcounts ways, giving wrong answer

✅ Process coins in order and update dp accordingly to avoid duplicates

Not handling base case dp[0] = 1

Results in zero ways for amount zero, breaking DP

✅ Initialize dp[0] = 1 to represent empty combination

Using 1D dp but iterating amounts backwards

Leads to counting permutations, not combinations

✅ Iterate amounts forwards when coins are unlimited

🧠

Brute Force (Pure Recursion)

💡 This approach helps understand the problem's structure by exploring all possible combinations recursively, though it is inefficient.

Intuition

Try every coin at each step and recursively count ways to form the remaining amount until zero or negative.

Algorithm

1. If amount is 0, return 1 (one valid combination).
2. If amount is negative or no coins left, return 0 (no valid combination).
3. Recursively count ways by including the current coin and excluding it.
4. Sum both counts to get total ways.

💡 The recursion tree grows exponentially because it explores all subsets, making it hard to track without memoization.

Recurrence:countWays(i, amount) = countWays(i+1, amount) + countWays(i, amount - coins[i])

</>

Code

def change(amount, coins):
    def dfs(i, amt):
        if amt == 0:
            return 1
        if amt < 0 or i == len(coins):
            return 0
        return dfs(i + 1, amt) + dfs(i, amt - coins[i])

    return dfs(0, amount)

# Example usage
if __name__ == '__main__':
    print(change(5, [1, 2, 5]))  # Output: 4

Line Notes

def dfs(i, amt):Defines recursive helper to explore coin choices starting at index i

if amt == 0:Base case: exact amount formed means one valid combination

if amt < 0 or i == len(coins):Base case: invalid path if amount negative or no coins left

return dfs(i + 1, amt) + dfs(i, amt - coins[i])Sum ways excluding and including current coin

public class Solution {
    public int change(int amount, int[] coins) {
        return dfs(coins, 0, amount);
    }

    private int dfs(int[] coins, int i, int amt) {
        if (amt == 0) return 1;
        if (amt < 0 || i == coins.length) return 0;
        return dfs(coins, i + 1, amt) + dfs(coins, i, amt - coins[i]);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.change(5, new int[]{1, 2, 5})); // Output: 4
    }
}

Line Notes

public int change(int amount, int[] coins)Entry point to start recursion

if (amt == 0) return 1;Found a valid combination

if (amt < 0 || i == coins.length) return 0;Invalid path or no coins left

return dfs(coins, i + 1, amt) + dfs(coins, i, amt - coins[i]);Explore excluding and including current coin

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

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        return dfs(coins, 0, amount);
    }

private:
    int dfs(vector<int>& coins, int i, int amt) {
        if (amt == 0) return 1;
        if (amt < 0 || i == coins.size()) return 0;
        return dfs(coins, i + 1, amt) + dfs(coins, i, amt - coins[i]);
    }
};

int main() {
    Solution sol;
    vector<int> coins = {1, 2, 5};
    cout << sol.change(5, coins) << endl; // Output: 4
    return 0;
}

Line Notes

int dfs(vector<int>& coins, int i, int amt)Recursive helper exploring coin choices

if (amt == 0) return 1;Base case: valid combination found

if (amt < 0 || i == coins.size()) return 0;Invalid or no coins left

return dfs(coins, i + 1, amt) + dfs(coins, i, amt - coins[i]);Sum ways excluding and including coin

function change(amount, coins) {
  function dfs(i, amt) {
    if (amt === 0) return 1;
    if (amt < 0 || i === coins.length) return 0;
    return dfs(i + 1, amt) + dfs(i, amt - coins[i]);
  }
  return dfs(0, amount);
}

// Example usage
console.log(change(5, [1, 2, 5])); // Output: 4

Line Notes

function dfs(i, amt)Recursive function to explore coin combinations

if (amt === 0) return 1;Found a valid way to form amount

if (amt < 0 || i === coins.length) return 0;Invalid path or no coins left

return dfs(i + 1, amt) + dfs(i, amt - coins[i]);Count ways excluding and including current coin

⏱

Complexity

TimeO(2^n) where n is amount, due to exploring all subsets

SpaceO(n) recursion stack depth

Each call branches into two, leading to exponential calls; stack depth is at most amount

💡 For amount=20, this means over a million calls, which is impractical.

Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem structure.

🧠

Top-Down Memoization

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

Intuition

Store results of recursive calls in a table keyed by coin index and remaining amount to reuse them.

Algorithm

1. Initialize a memo table to store results for each (index, amount) pair.
2. If amount is 0, return 1.
3. If amount is negative or no coins left, return 0.
4. If result is cached, return it.
5. Otherwise, compute ways by excluding and including current coin, cache and return.

💡 Memoization turns exponential recursion into polynomial by pruning duplicate calls.

Recurrence:dp[i][amt] = dp[i+1][amt] + dp[i][amt - coins[i]]

</>

Code

def change(amount, coins):
    memo = {}
    def dfs(i, amt):
        if amt == 0:
            return 1
        if amt < 0 or i == len(coins):
            return 0
        if (i, amt) in memo:
            return memo[(i, amt)]
        memo[(i, amt)] = dfs(i + 1, amt) + dfs(i, amt - coins[i])
        return memo[(i, amt)]

    return dfs(0, amount)

if __name__ == '__main__':
    print(change(5, [1, 2, 5]))  # Output: 4

Line Notes

memo = {}Cache to store computed results for subproblems

if (i, amt) in memo:Return cached result to avoid recomputation

memo[(i, amt)] = dfs(i + 1, amt) + dfs(i, amt - coins[i])Store computed ways including and excluding coin

return memo[(i, amt)]Return cached or newly computed result

import java.util.*;

public class Solution {
    private Map<String, Integer> memo = new HashMap<>();

    public int change(int amount, int[] coins) {
        return dfs(coins, 0, amount);
    }

    private int dfs(int[] coins, int i, int amt) {
        if (amt == 0) return 1;
        if (amt < 0 || i == coins.length) return 0;
        String key = i + "," + amt;
        if (memo.containsKey(key)) return memo.get(key);
        int res = dfs(coins, i + 1, amt) + dfs(coins, i, amt - coins[i]);
        memo.put(key, res);
        return res;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.change(5, new int[]{1, 2, 5})); // Output: 4
    }
}

Line Notes

private Map<String, Integer> memo = new HashMap<>();Memo cache keyed by coin index and amount

String key = i + "," + amt;Create unique key for current subproblem

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

memo.put(key, res);Store computed result to avoid recomputation

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

class Solution {
    unordered_map<string, int> memo;
public:
    int change(int amount, vector<int>& coins) {
        return dfs(coins, 0, amount);
    }

private:
    int dfs(vector<int>& coins, int i, int amt) {
        if (amt == 0) return 1;
        if (amt < 0 || i == coins.size()) return 0;
        string key = to_string(i) + "," + to_string(amt);
        if (memo.count(key)) return memo[key];
        memo[key] = dfs(coins, i + 1, amt) + dfs(coins, i, amt - coins[i]);
        return memo[key];
    }
};

int main() {
    Solution sol;
    vector<int> coins = {1, 2, 5};
    cout << sol.change(5, coins) << endl; // Output: 4
    return 0;
}

Line Notes

unordered_map<string, int> memo;Cache for storing subproblem results

string key = to_string(i) + "," + to_string(amt);Unique key for memoization

if (memo.count(key)) return memo[key];Return cached result if present

memo[key] = dfs(coins, i + 1, amt) + dfs(coins, i, amt - coins[i]);Store computed ways

function change(amount, coins) {
  const memo = new Map();
  function dfs(i, amt) {
    if (amt === 0) return 1;
    if (amt < 0 || i === coins.length) return 0;
    const key = i + ',' + amt;
    if (memo.has(key)) return memo.get(key);
    const res = dfs(i + 1, amt) + dfs(i, amt - coins[i]);
    memo.set(key, res);
    return res;
  }
  return dfs(0, amount);
}

console.log(change(5, [1, 2, 5])); // Output: 4

Line Notes

const memo = new Map();Memo cache to store subproblem results

const key = i + ',' + amt;Unique key for current subproblem

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

memo.set(key, res);Cache computed result for reuse

⏱

Complexity

TimeO(n * amount) where n is number of coins

SpaceO(n * amount) for memo table and recursion stack

Memoization ensures each subproblem computed once; total subproblems = n*amount

💡 For amount=20 and 3 coins, at most 60 subproblems computed, much faster than brute force.

Interview Verdict: Accepted

This approach is efficient enough for most inputs and a good first optimization.

🧠

Bottom-Up Tabulation

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

Intuition

Use a 2D dp table where dp[i][w] stores ways to make amount w using first i coins, fill table row by row.

Algorithm

1. Initialize dp table with dp[0][0] = 1 (one way to make amount 0 with 0 coins).
2. Iterate over coins (rows) and amounts (columns).
3. For each cell, ways = ways excluding current coin + ways including current coin if possible.
4. Return dp[number_of_coins][amount] as final answer.

💡 This approach explicitly shows how subproblems build up to the final solution.

Recurrence:dp[i][w] = dp[i-1][w] + (w >= coins[i-1] ? dp[i][w - coins[i-1]] : 0)

</>

Code

def change(amount, coins):
    n = len(coins)
    dp = [[0] * (amount + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = 1

    for i in range(1, n + 1):
        for w in range(amount + 1):
            dp[i][w] = dp[i - 1][w]
            if w >= coins[i - 1]:
                dp[i][w] += dp[i][w - coins[i - 1]]

    return dp[n][amount]

if __name__ == '__main__':
    print(change(5, [1, 2, 5]))  # Output: 4

Line Notes

dp = [[0] * (amount + 1) for _ in range(n + 1)]Create 2D DP table for coins and amounts

for i in range(n + 1): dp[i][0] = 1Base case: one way to make amount 0 with any coins

dp[i][w] = dp[i - 1][w]Ways excluding current coin

dp[i][w] += dp[i][w - coins[i - 1]]Add ways including current coin if possible

public class Solution {
    public int change(int amount, int[] coins) {
        int n = coins.length;
        int[][] dp = new int[n + 1][amount + 1];
        for (int i = 0; i <= n; i++) dp[i][0] = 1;

        for (int i = 1; i <= n; i++) {
            for (int w = 0; w <= amount; w++) {
                dp[i][w] = dp[i - 1][w];
                if (w >= coins[i - 1]) dp[i][w] += dp[i][w - coins[i - 1]];
            }
        }
        return dp[n][amount];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.change(5, new int[]{1, 2, 5})); // Output: 4
    }
}

Line Notes

int[][] dp = new int[n + 1][amount + 1];2D DP array for subproblems

for (int i = 0; i <= n; i++) dp[i][0] = 1;Base case initialization

dp[i][w] = dp[i - 1][w];Exclude current coin ways

if (w >= coins[i - 1]) dp[i][w] += dp[i][w - coins[i - 1]];Include current coin ways if possible

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

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        vector<vector<int>> dp(n + 1, vector<int>(amount + 1, 0));
        for (int i = 0; i <= n; i++) dp[i][0] = 1;

        for (int i = 1; i <= n; i++) {
            for (int w = 0; w <= amount; w++) {
                dp[i][w] = dp[i - 1][w];
                if (w >= coins[i - 1]) dp[i][w] += dp[i][w - coins[i - 1]];
            }
        }
        return dp[n][amount];
    }
};

int main() {
    Solution sol;
    vector<int> coins = {1, 2, 5};
    cout << sol.change(5, coins) << endl; // Output: 4
    return 0;
}

Line Notes

vector<vector<int>> dp(n + 1, vector<int>(amount + 1, 0));Initialize DP table with zeros

for (int i = 0; i <= n; i++) dp[i][0] = 1;Base case: one way to make amount 0

dp[i][w] = dp[i - 1][w];Ways excluding current coin

if (w >= coins[i - 1]) dp[i][w] += dp[i][w - coins[i - 1]];Add ways including current coin

function change(amount, coins) {
  const n = coins.length;
  const dp = Array.from({ length: n + 1 }, () => Array(amount + 1).fill(0));
  for (let i = 0; i <= n; i++) dp[i][0] = 1;

  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= amount; w++) {
      dp[i][w] = dp[i - 1][w];
      if (w >= coins[i - 1]) dp[i][w] += dp[i][w - coins[i - 1]];
    }
  }
  return dp[n][amount];
}

console.log(change(5, [1, 2, 5])); // Output: 4

Line Notes

const dp = Array.from({ length: n + 1 }, () => Array(amount + 1).fill(0));Create 2D DP array initialized to zero

for (let i = 0; i <= n; i++) dp[i][0] = 1;Base case initialization

dp[i][w] = dp[i - 1][w];Exclude current coin ways

if (w >= coins[i - 1]) dp[i][w] += dp[i][w - coins[i - 1]];Include current coin ways if possible

⏱

Complexity

TimeO(n * amount)

SpaceO(n * amount)

We fill a table of size n by amount once, each cell computed in O(1)

💡 For n=3 and amount=5, only 18 cells computed, very efficient.

Interview Verdict: Accepted

This is the standard DP solution for this problem and is interview-ready.

🧠

Space Optimized Bottom-Up DP

💡 We can reduce space from 2D to 1D by iterating amounts in order and updating ways in place, leveraging the unbounded nature of coins.

Intuition

Use a 1D dp array where dp[w] stores ways to make amount w; update dp for each coin by adding ways to make w - coin.

Algorithm

1. Initialize dp array of size amount+1 with dp[0] = 1.
2. For each coin, iterate amounts from coin value to amount.
3. Update dp[w] by adding dp[w - coin] to include new combinations.
4. Return dp[amount] as the total number of ways.

💡 This approach efficiently accumulates counts without storing full 2D table.

Recurrence:dp[w] += dp[w - coin]

</>

Code

def change(amount, coins):
    dp = [0] * (amount + 1)
    dp[0] = 1
    for coin in coins:
        for w in range(coin, amount + 1):
            dp[w] += dp[w - coin]
    return dp[amount]

if __name__ == '__main__':
    print(change(5, [1, 2, 5]))  # Output: 4

Line Notes

dp = [0] * (amount + 1)Initialize 1D dp array for amounts

dp[0] = 1Base case: one way to make amount 0

for coin in coins:Process each coin one by one

dp[w] += dp[w - coin]Add ways including current coin

public class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int w = coin; w <= amount; w++) {
                dp[w] += dp[w - coin];
            }
        }
        return dp[amount];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.change(5, new int[]{1, 2, 5})); // Output: 4
    }
}

Line Notes

int[] dp = new int[amount + 1];1D dp array for storing ways

dp[0] = 1;Base case initialization

for (int coin : coins)Iterate over each coin

dp[w] += dp[w - coin];Update ways including current coin

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

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1, 0);
        dp[0] = 1;
        for (int coin : coins) {
            for (int w = coin; w <= amount; w++) {
                dp[w] += dp[w - coin];
            }
        }
        return dp[amount];
    }
};

int main() {
    Solution sol;
    vector<int> coins = {1, 2, 5};
    cout << sol.change(5, coins) << endl; // Output: 4
    return 0;
}

Line Notes

vector<int> dp(amount + 1, 0);1D dp vector initialized to zero

dp[0] = 1;Base case: one way to make zero amount

for (int coin : coins)Process each coin

dp[w] += dp[w - coin];Add ways including current coin

function change(amount, coins) {
  const dp = Array(amount + 1).fill(0);
  dp[0] = 1;
  for (const coin of coins) {
    for (let w = coin; w <= amount; w++) {
      dp[w] += dp[w - coin];
    }
  }
  return dp[amount];
}

console.log(change(5, [1, 2, 5])); // Output: 4

Line Notes

const dp = Array(amount + 1).fill(0);Initialize 1D dp array

dp[0] = 1;Base case initialization

for (const coin of coins)Iterate over coins

dp[w] += dp[w - coin];Update ways including current coin

⏱

Complexity

TimeO(n * amount)

SpaceO(amount)

Single dp array updated for each coin and amount combination

💡 For amount=20 and 3 coins, only 60 updates needed, very space efficient.

Interview Verdict: Accepted

This is the most optimal approach in terms of space and is preferred in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, coding the space optimized DP is ideal after explaining brute force and memoization briefly.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n)	O(n) recursion stack	Yes (deep recursion)	N/A	Mention only - never code
2. Top-Down Memoization	O(n * amount)	O(n * amount)	No (memo pruning)	Yes with extra tracking	Good first coding approach
3. Bottom-Up Tabulation	O(n * amount)	O(n * amount)	No	Yes with extra tracking	Standard DP solution
4. Space Optimized DP	O(n * amount)	O(amount)	No	Harder, needs extra bookkeeping	Best for final implementation

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify problem constraints and examples.Explain brute force recursion to show understanding.Introduce memoization to optimize recursion.Present bottom-up tabulation for iterative clarity.Finally, show space optimization for best efficiency.Test code with examples and edge cases.

Time Allocation

Clarify: 2min → Brute Force: 5min → Memoization: 5min → Tabulation: 5min → Space Optimization: 3min → Testing: 5min. Total ~25min

What the Interviewer Tests

Understanding of DP concepts, ability to optimize naive solutions, and clarity in explaining tradeoffs.

Common Follow-ups

• What if order of coins matters? → Use permutations counting approach.
• How to reconstruct one combination? → Store choices in DP and backtrack.

💡 These follow-ups test deeper understanding of DP variations and solution reconstruction.

🔍

Pattern Recognition

When to Use

1) Problem asks for number of ways/combinations; 2) Unlimited usage of items (coins); 3) Target sum or amount; 4) Order does not matter.

Signature Phrases

number of combinationsunlimited coinsmake up amountorder does not matter

NOT This Pattern When

Problems asking for permutations or limited usage of coins are different patterns.

Similar Problems

Coin Change I - minimum coins neededCombination Sum IV - count permutationsPartition Equal Subset Sum - subset sum problem

Practice

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

3. You are given a list of days when you will travel and three types of tickets with different durations and costs. You want to minimize the total cost to cover all travel days. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Dynamic programming using bottom-up tabulation with binary search to find the next uncovered day

B. Greedy algorithm that always buys the cheapest ticket for the current day

C. Pure recursion without memoization, exploring all ticket combinations

D. Sorting days and using a sliding window to pick tickets covering maximum days

Solution

1. Step 1: Understand problem constraints

   The problem requires covering all travel days with minimum cost, where tickets have different durations and costs.

2. Step 2: Identify suitable algorithm

   Greedy fails because cheapest ticket today may not cover future days optimally. Pure recursion is exponential and inefficient. Sliding window doesn't handle overlapping durations well. Bottom-up DP with binary search efficiently finds next uncovered day and computes minimal cost.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP with binary search ensures optimal substructure and efficient lookup [OK]

Hint: Optimal solution requires DP with binary search [OK]

Common Mistakes:

• Assuming greedy always works
• Ignoring overlapping ticket durations
• Using recursion without memoization

4. What is the time complexity of the bottom-up DP solution with binary search for the minimum cost tickets problem, given n travel days?

medium

A. O(n^2) because for each day we scan all future days

B. O(n log n) because for each day we perform 3 binary searches over the days array

C. O(n) because we only iterate once over the days array

D. O(n * 3 * n) due to nested loops over days and durations

Solution

1. Step 1: Identify loops and operations

   Outer loop runs n times (for each day). Inner loop runs 3 times (for each ticket duration). Each inner iteration does a binary search (log n) to find next uncovered day.

2. Step 2: Calculate total complexity

   Total time = n * 3 * log n = O(n log n). Linear scan or nested loops over days would be O(n^2), but binary search reduces it.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Binary search reduces inner loop from O(n) to O(log n) [OK]

Hint: Binary search reduces complexity from quadratic to n log n [OK]

Common Mistakes:

• Assuming inner loop is linear scan
• Ignoring binary search effect
• Confusing space with time complexity

5. Suppose the problem is modified so that each ticket can be used multiple times but only on distinct travel days (no overlapping coverage). Which modification to the algorithm is necessary to handle this constraint correctly?

hard

A. Use a top-down DP with memoization and add a visited set to track used tickets

B. Change binary search to linear scan to find next uncovered day to avoid reuse overlap

C. Modify DP state to include the last day covered and ensure no overlapping ticket durations

D. No change needed; the existing bottom-up DP with binary search works as is

Solution

1. Step 1: Understand new constraint

   Tickets can be reused but cannot overlap coverage on travel days. This requires tracking coverage intervals explicitly.

2. Step 2: Modify DP state

   DP must include last covered day or interval to ensure no overlapping coverage. Without this, DP may double count days or reuse tickets incorrectly.

3. Step 3: Evaluate other options

   Adding visited sets or linear scans is inefficient or insufficient. Existing DP assumes unlimited overlapping coverage, so no change is incorrect.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   DP state must track coverage to prevent overlap [OK]

Hint: Track coverage intervals in DP state for reuse constraints [OK]

Common Mistakes:

• Assuming no change needed
• Using visited sets without DP state change
• Replacing binary search with linear scan