Best Time - Cooldown

🎯

Best Time - Cooldown

mediumDPAmazonGoogleSnap

Imagine you are a stock trader who wants to maximize profit but must rest one day after selling before buying again. How do you plan your trades?

💡 This problem is a classic example of dynamic programming with state machines. Beginners often struggle because the cooldown constraint breaks simple greedy strategies and requires tracking multiple states over time.

📋

Problem Statement

You are given an array prices where prices[i] is the price of a given stock on the i-th day. Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following restrictions: After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day). Return the maximum profit you can achieve.

1 ≤ prices.length ≤ 10^50 ≤ prices[i] ≤ 10^4

💡

Example

Input"[1,2,3,0,2]"

Output3

Buy on day 0, sell on day 1, cooldown day 2, buy on day 3, sell on day 4, total profit = 3.

• Single day prices → profit is 0 because no transactions possible
• All prices are the same → profit is 0 because no gain from transactions
• Strictly decreasing prices → profit is 0 because no profitable transactions
• Prices with multiple peaks and valleys → test cooldown logic correctness

🔁

Why DP?

Why greedy fails:

A greedy approach that buys at every local minimum and sells at every local maximum fails because it ignores the cooldown day. For example, prices = [1,2,3,0,2], greedy would buy day 0 sell day 2 and then buy day 3 immediately, which is invalid due to cooldown.

DP state:

dp[i][state] represents the maximum profit achievable on day i when in a particular state (holding stock, in cooldown, or free to buy).

Recurrence:dp[i][0] = max(dp[i-1][0], dp[i-1][2] - prices[i]) dp[i][1] = dp[i-1][0] + prices[i] dp[i][2] = max(dp[i-1][1], dp[i-1][2])

On day i, holding stock means either we held it yesterday or bought today after cooldown; not holding means we sold today or are in cooldown; cooldown means we just sold yesterday or stayed in cooldown.

⚠️

Common Mistakes

Ignoring cooldown day after selling

Incorrect profit calculation, often overestimating profit

✅ Explicitly model cooldown state or skip day after sell

Using greedy approach to buy/sell at every local min/max

Fails on test cases with cooldown, producing wrong answers

✅ Use DP to track states and cooldown constraints

Not memoizing recursive calls

Exponential time causing TLE on large inputs

✅ Add memo dictionary keyed by day and holding state

Incorrect base cases or indexing in DP arrays

Runtime errors or wrong results

✅ Carefully initialize day 0 states and handle array bounds

Mixing up states or transitions in DP

Logic errors leading to incorrect profits

✅ Clearly define and document each state and allowed transitions

🧠

Brute Force (Pure Recursion)

💡 This approach explores all possible buy, sell, and cooldown sequences recursively. It is slow but helps understand the problem's state transitions and why DP is needed.

Intuition

At each day, decide to buy, sell, or cooldown based on current state and recursively compute max profit for remaining days.

Algorithm

1. Define a recursive function with current day and holding state.
2. If day is beyond last, return 0 profit.
3. If holding stock, choose to sell or cooldown.
4. If not holding, choose to buy or cooldown.
5. Return max profit from these choices.

💡 The recursion explores all action sequences but repeats many states, causing exponential time.

Recurrence:f(i, holding) = max( if holding: sell + f(i+2, false), cooldown + f(i+1, true) else: buy + f(i+1, true), cooldown + f(i+1, false) )

</>

Code

def maxProfit(prices):
    n = len(prices)
    def dfs(i, holding):
        if i >= n:
            return 0
        if holding:
            sell = prices[i] + dfs(i+2, False)
            cooldown = dfs(i+1, True)
            return max(sell, cooldown)
        else:
            buy = -prices[i] + dfs(i+1, True)
            cooldown = dfs(i+1, False)
            return max(buy, cooldown)
    return dfs(0, False)

# Example usage
if __name__ == '__main__':
    print(maxProfit([1,2,3,0,2]))  # Output: 3

Line Notes

def dfs(i, holding):Defines recursive helper with day and holding state

if i >= n:Base case: no more days means no profit

if holding:If holding stock, can sell or cooldown

sell = prices[i] + dfs(i+2, False)Selling today adds price and skips next day due to cooldown

buy = -prices[i] + dfs(i+1, True)Buying today costs price and moves to holding state

return dfs(0, False)Start recursion from day 0 without holding

public class Solution {
    public int maxProfit(int[] prices) {
        return dfs(prices, 0, false);
    }
    private int dfs(int[] prices, int i, boolean holding) {
        if (i >= prices.length) return 0;
        if (holding) {
            int sell = prices[i] + dfs(prices, i + 2, false);
            int cooldown = dfs(prices, i + 1, true);
            return Math.max(sell, cooldown);
        } else {
            int buy = -prices[i] + dfs(prices, i + 1, true);
            int cooldown = dfs(prices, i + 1, false);
            return Math.max(buy, cooldown);
        }
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.maxProfit(new int[]{1,2,3,0,2})); // 3
    }
}

Line Notes

public int maxProfit(int[] prices)Entry point calling recursive helper

if (i >= prices.length) return 0;Base case: no days left

if (holding)If holding stock, decide to sell or cooldown

int sell = prices[i] + dfs(prices, i + 2, false);Sell today and cooldown next day

return Math.max(buy, cooldown);Choose best action profit

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

class Solution {
public:
    int dfs(const vector<int>& prices, int i, bool holding) {
        if (i >= prices.size()) return 0;
        if (holding) {
            int sell = prices[i] + dfs(prices, i + 2, false);
            int cooldown = dfs(prices, i + 1, true);
            return max(sell, cooldown);
        } else {
            int buy = -prices[i] + dfs(prices, i + 1, true);
            int cooldown = dfs(prices, i + 1, false);
            return max(buy, cooldown);
        }
    }
    int maxProfit(vector<int>& prices) {
        return dfs(prices, 0, false);
    }
};

int main() {
    Solution sol;
    vector<int> prices = {1,2,3,0,2};
    cout << sol.maxProfit(prices) << endl; // 3
    return 0;
}

Line Notes

int dfs(const vector<int>& prices, int i, bool holding)Recursive helper with day and holding state

if (i >= prices.size()) return 0;Base case: no days left

if (holding)If holding, can sell or cooldown

int sell = prices[i] + dfs(prices, i + 2, false);Sell today and cooldown next day

return max(buy, cooldown);Choose best profit action

var maxProfit = function(prices) {
    const n = prices.length;
    function dfs(i, holding) {
        if (i >= n) return 0;
        if (holding) {
            const sell = prices[i] + dfs(i + 2, false);
            const cooldown = dfs(i + 1, true);
            return Math.max(sell, cooldown);
        } else {
            const buy = -prices[i] + dfs(i + 1, true);
            const cooldown = dfs(i + 1, false);
            return Math.max(buy, cooldown);
        }
    }
    return dfs(0, false);
};

// Example usage
console.log(maxProfit([1,2,3,0,2])); // 3

Line Notes

function dfs(i, holding)Recursive function with day and holding state

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

if (holding)If holding stock, decide sell or cooldown

const sell = prices[i] + dfs(i + 2, false);Sell today and cooldown next day

return dfs(0, false);Start recursion from day 0 without holding

⏱

Complexity

TimeO(2^n) exponential due to exploring all buy/sell/cooldown sequences

SpaceO(n) recursion stack depth

Each day has two states (holding or not), branching into two choices, leading to exponential calls

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

Interview Verdict: TLE

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

🧠

Top-Down DP with Memoization

💡 Memoization caches results of recursive calls to avoid recomputing states, drastically improving performance while keeping the recursive intuition.

Intuition

Store results of dfs(day, holding) in a cache so repeated calls return instantly, reducing exponential to linear time.

Algorithm

1. Define recursive function with day and holding state.
2. Use a memo dictionary keyed by (day, holding) to store results.
3. If result cached, return it immediately.
4. Otherwise compute as in brute force and cache before returning.

💡 Memoization turns exponential recursion into linear by remembering past results.

Recurrence:Same as brute force but with caching to avoid recomputation.

</>

Code

def maxProfit(prices):
    n = len(prices)
    memo = {}
    def dfs(i, holding):
        if i >= n:
            return 0
        if (i, holding) in memo:
            return memo[(i, holding)]
        if holding:
            sell = prices[i] + dfs(i+2, False)
            cooldown = dfs(i+1, True)
            memo[(i, holding)] = max(sell, cooldown)
        else:
            buy = -prices[i] + dfs(i+1, True)
            cooldown = dfs(i+1, False)
            memo[(i, holding)] = max(buy, cooldown)
        return memo[(i, holding)]
    return dfs(0, False)

if __name__ == '__main__':
    print(maxProfit([1,2,3,0,2]))  # 3

Line Notes

memo = {}Initialize cache to store computed states

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

memo[(i, holding)] = max(sell, cooldown)Cache computed result before returning

return dfs(0, False)Start recursion with memoization

import java.util.*;
public class Solution {
    private Map<String, Integer> memo = new HashMap<>();
    public int maxProfit(int[] prices) {
        return dfs(prices, 0, false);
    }
    private int dfs(int[] prices, int i, boolean holding) {
        if (i >= prices.length) return 0;
        String key = i + "," + holding;
        if (memo.containsKey(key)) return memo.get(key);
        int res;
        if (holding) {
            int sell = prices[i] + dfs(prices, i + 2, false);
            int cooldown = dfs(prices, i + 1, true);
            res = Math.max(sell, cooldown);
        } else {
            int buy = -prices[i] + dfs(prices, i + 1, true);
            int cooldown = dfs(prices, i + 1, false);
            res = Math.max(buy, cooldown);
        }
        memo.put(key, res);
        return res;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.maxProfit(new int[]{1,2,3,0,2})); // 3
    }
}

Line Notes

private Map<String, Integer> memo = new HashMap<>();Cache to store results keyed by day and holding

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

memo.put(key, res);Store computed result before returning

return dfs(prices, 0, false);Start memoized recursion

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

class Solution {
    unordered_map<string,int> memo;
    int dfs(const vector<int>& prices, int i, bool holding) {
        if (i >= prices.size()) return 0;
        string key = to_string(i) + "," + (holding ? "1" : "0");
        if (memo.count(key)) return memo[key];
        int res;
        if (holding) {
            int sell = prices[i] + dfs(prices, i + 2, false);
            int cooldown = dfs(prices, i + 1, true);
            res = max(sell, cooldown);
        } else {
            int buy = -prices[i] + dfs(prices, i + 1, true);
            int cooldown = dfs(prices, i + 1, false);
            res = max(buy, cooldown);
        }
        memo[key] = res;
        return res;
    }
public:
    int maxProfit(vector<int>& prices) {
        return dfs(prices, 0, false);
    }
};

int main() {
    Solution sol;
    vector<int> prices = {1,2,3,0,2};
    cout << sol.maxProfit(prices) << endl; // 3
    return 0;
}

Line Notes

unordered_map<string,int> memo;Cache for memoization keyed by day and holding

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

memo[key] = res;Store computed result

return dfs(prices, 0, false);Start memoized recursion

var maxProfit = function(prices) {
    const n = prices.length;
    const memo = new Map();
    function dfs(i, holding) {
        if (i >= n) return 0;
        const key = i + ',' + holding;
        if (memo.has(key)) return memo.get(key);
        let res;
        if (holding) {
            const sell = prices[i] + dfs(i + 2, false);
            const cooldown = dfs(i + 1, true);
            res = Math.max(sell, cooldown);
        } else {
            const buy = -prices[i] + dfs(i + 1, true);
            const cooldown = dfs(i + 1, false);
            res = Math.max(buy, cooldown);
        }
        memo.set(key, res);
        return res;
    }
    return dfs(0, false);
};

console.log(maxProfit([1,2,3,0,2])); // 3

Line Notes

const memo = new Map();Cache to store computed states

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

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

return dfs(0, false);Start memoized recursion

⏱

Complexity

TimeO(n) because each day and holding state is computed once

SpaceO(n) for recursion stack and memo storage

Memoization reduces exponential calls to linear by caching results for each (day, holding) pair

💡 For n=20, this means about 40 calls, a huge improvement over brute force.

Interview Verdict: Accepted

This approach is efficient enough for large inputs and retains recursive clarity.

🧠

Bottom-Up DP (Tabulation with State Machine)

💡 This approach uses iterative DP with explicit states to build the solution from day 0 to n-1, avoiding recursion and improving clarity and efficiency.

Intuition

Track three states per day: holding stock, in cooldown, and free to buy. Update these states iteratively using previous day values.

Algorithm

1. Initialize dp arrays for holding, cooldown, and free states.
2. Iterate over each day updating states based on previous day.
3. Holding: max of holding yesterday or buying today from free state.
4. Cooldown: selling stock today from holding yesterday.
5. Free: max of free yesterday or cooldown yesterday.

💡 This approach explicitly models the problem states and transitions, making it easier to understand and debug.

Recurrence:hold[i] = max(hold[i-1], free[i-1] - prices[i]) cool[i] = hold[i-1] + prices[i] free[i] = max(free[i-1], cool[i-1])

</>

Code

def maxProfit(prices):
    n = len(prices)
    if n == 0:
        return 0
    hold = [0]*n
    cool = [0]*n
    free = [0]*n
    hold[0] = -prices[0]
    for i in range(1, n):
        hold[i] = max(hold[i-1], free[i-1] - prices[i])
        cool[i] = hold[i-1] + prices[i]
        free[i] = max(free[i-1], cool[i-1])
    return max(cool[-1], free[-1])

if __name__ == '__main__':
    print(maxProfit([1,2,3,0,2]))  # 3

Line Notes

hold = [0]*nArray to track max profit holding stock on day i

hold[0] = -prices[0]Buying on first day sets holding profit negative

hold[i] = max(hold[i-1], free[i-1] - prices[i])Hold or buy today from free state

return max(cool[-1], free[-1])Max profit is max of cooldown or free on last day

public class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if (n == 0) return 0;
        int[] hold = new int[n];
        int[] cool = new int[n];
        int[] free = new int[n];
        hold[0] = -prices[0];
        for (int i = 1; i < n; i++) {
            hold[i] = Math.max(hold[i-1], free[i-1] - prices[i]);
            cool[i] = hold[i-1] + prices[i];
            free[i] = Math.max(free[i-1], cool[i-1]);
        }
        return Math.max(cool[n-1], free[n-1]);
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.maxProfit(new int[]{1,2,3,0,2})); // 3
    }
}

Line Notes

int[] hold = new int[n];Track max profit holding stock day i

hold[0] = -prices[0];Buying on first day

hold[i] = Math.max(hold[i-1], free[i-1] - prices[i]);Hold or buy today from free state

return Math.max(cool[n-1], free[n-1]);Max profit at last day is cooldown or free

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

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n == 0) return 0;
        vector<int> hold(n), cool(n), free(n);
        hold[0] = -prices[0];
        for (int i = 1; i < n; i++) {
            hold[i] = max(hold[i-1], free[i-1] - prices[i]);
            cool[i] = hold[i-1] + prices[i];
            free[i] = max(free[i-1], cool[i-1]);
        }
        return max(cool[n-1], free[n-1]);
    }
};

int main() {
    Solution sol;
    vector<int> prices = {1,2,3,0,2};
    cout << sol.maxProfit(prices) << endl; // 3
    return 0;
}

Line Notes

vector<int> hold(n), cool(n), free(n);Arrays for each state profit per day

hold[0] = -prices[0];Buy on first day

hold[i] = max(hold[i-1], free[i-1] - prices[i]);Hold or buy today from free state

return max(cool[n-1], free[n-1]);Max profit is cooldown or free last day

var maxProfit = function(prices) {
    const n = prices.length;
    if (n === 0) return 0;
    const hold = new Array(n).fill(0);
    const cool = new Array(n).fill(0);
    const free = new Array(n).fill(0);
    hold[0] = -prices[0];
    for (let i = 1; i < n; i++) {
        hold[i] = Math.max(hold[i-1], free[i-1] - prices[i]);
        cool[i] = hold[i-1] + prices[i];
        free[i] = Math.max(free[i-1], cool[i-1]);
    }
    return Math.max(cool[n-1], free[n-1]);
};

console.log(maxProfit([1,2,3,0,2])); // 3

Line Notes

const hold = new Array(n).fill(0);Track holding profit per day

hold[0] = -prices[0];Buy on first day

hold[i] = Math.max(hold[i-1], free[i-1] - prices[i]);Hold or buy today from free state

return Math.max(cool[n-1], free[n-1]);Max profit is cooldown or free last day

⏱

Complexity

TimeO(n) iterating once through prices

SpaceO(n) for dp arrays

Each day updates three states in constant time, total linear time

💡 For n=100000, this is efficient and practical.

Interview Verdict: Accepted

This is the standard efficient solution preferred in interviews for clarity and iterative style.

🧠

Space Optimized Bottom-Up DP

💡 Since each day depends only on previous day states, we can reduce space from O(n) to O(1) by storing only last day states.

Intuition

Keep track of only previous day's hold, cool, and free states and update them iteratively.

Algorithm

1. Initialize variables hold, cool, free for day 0.
2. Iterate from day 1 to n-1 updating new hold, cool, free from previous values.
3. Assign updated values back to variables for next iteration.
4. Return max of cool and free after last day.

💡 This reduces memory usage while preserving the logic and correctness of the DP.

Recurrence:Same as bottom-up but using variables instead of arrays.

</>

Code

def maxProfit(prices):
    n = len(prices)
    if n == 0:
        return 0
    hold = -prices[0]
    cool = 0
    free = 0
    for i in range(1, n):
        prev_hold = hold
        hold = max(hold, free - prices[i])
        free = max(free, cool)
        cool = prev_hold + prices[i]
    return max(cool, free)

if __name__ == '__main__':
    print(maxProfit([1,2,3,0,2]))  # 3

Line Notes

hold = -prices[0]Initialize holding state after buying first day

prev_hold = holdStore previous hold before updating

hold = max(hold, free - prices[i])Update hold: keep or buy today from free state

return max(cool, free)Max profit is cooldown or free last day

public class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if (n == 0) return 0;
        int hold = -prices[0], cool = 0, free = 0;
        for (int i = 1; i < n; i++) {
            int prev_hold = hold;
            hold = Math.max(hold, free - prices[i]);
            free = Math.max(free, cool);
            cool = prev_hold + prices[i];
        }
        return Math.max(cool, free);
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.maxProfit(new int[]{1,2,3,0,2})); // 3
    }
}

Line Notes

int hold = -prices[0], cool = 0, free = 0;Initialize states for day 0

int prev_hold = hold;Save previous hold before update

hold = Math.max(hold, free - prices[i]);Update hold state: keep or buy today

return Math.max(cool, free);Return max profit after last day

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

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n == 0) return 0;
        int hold = -prices[0], cool = 0, free = 0;
        for (int i = 1; i < n; i++) {
            int prev_hold = hold;
            hold = max(hold, free - prices[i]);
            free = max(free, cool);
            cool = prev_hold + prices[i];
        }
        return max(cool, free);
    }
};

int main() {
    Solution sol;
    vector<int> prices = {1,2,3,0,2};
    cout << sol.maxProfit(prices) << endl; // 3
    return 0;
}

Line Notes

int hold = -prices[0], cool = 0, free = 0;Initialize states for day 0

int prev_hold = hold;Save previous hold before updating

hold = max(hold, free - prices[i]);Update hold state: keep or buy today

return max(cool, free);Return max profit after last day

var maxProfit = function(prices) {
    const n = prices.length;
    if (n === 0) return 0;
    let hold = -prices[0], cool = 0, free = 0;
    for (let i = 1; i < n; i++) {
        let prev_hold = hold;
        hold = Math.max(hold, free - prices[i]);
        free = Math.max(free, cool);
        cool = prev_hold + prices[i];
    }
    return Math.max(cool, free);
};

console.log(maxProfit([1,2,3,0,2])); // 3

Line Notes

let hold = -prices[0], cool = 0, free = 0;Initialize states for day 0

let prev_hold = hold;Save previous hold before update

hold = Math.max(hold, free - prices[i]);Update hold state: keep or buy today

return Math.max(cool, free);Return max profit after last day

⏱

Complexity

TimeO(n) single pass through prices

SpaceO(1) only constant variables used

Only previous day states stored, reducing memory usage drastically

💡 For very large n, this is the most efficient approach.

Interview Verdict: Accepted

This is the optimal solution in both time and space, ideal for interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 Memoization or bottom-up DP are best to code in interviews; brute force is only for explanation.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n)	O(n) recursion stack	Yes (deep recursion)	No	Mention only - never code
2. Top-Down DP with Memoization	O(n)	O(n) memo + recursion stack	Possible but unlikely for n=10^5	Yes with extra tracking	Good for recursive clarity and optimization
3. Bottom-Up DP (Tabulation)	O(n)	O(n)	No	Yes	Preferred for clarity and iterative style
4. Space Optimized Bottom-Up DP	O(n)	O(1)	No	Harder without extra tracking	Best for optimal performance

💼

Interview Strategy

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

How to Present

Clarify problem constraints and cooldown rule.Explain brute force recursion to show problem states.Introduce memoization to optimize recursion.Present bottom-up DP for clarity and efficiency.Finally, show space optimization for best performance.

Time Allocation

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

What the Interviewer Tests

Understanding of state machine DP, ability to optimize recursion, and clarity in explaining transitions and tradeoffs.

Common Follow-ups

• What if cooldown is 2 days? → Extend state machine with more cooldown states.
• What if transaction fee applies? → Modify state transitions to subtract fee on sell.
• Can you reconstruct the sequence of transactions? → Track decisions in DP arrays.
• What if only one transaction allowed? → Simplify to single buy/sell max profit.

💡 These follow-ups test your ability to adapt DP models and handle variations common in stock trading problems.

🔍

Pattern Recognition

When to Use

1) Problem involves stock buy/sell with constraints; 2) Multiple transactions allowed; 3) Cooldown or waiting period after sell; 4) Maximize profit over days.

Signature Phrases

'You cannot buy stock on the day after you sell it''Maximize profit with cooldown period'

NOT This Pattern When

Problems with only one transaction or no cooldown are simpler and use different DP or greedy approaches.

Similar Problems

Best Time to Buy and Sell Stock II - no cooldown, simpler DPBest Time to Buy and Sell Stock with Transaction Fee - similar state machine with feeBest Time to Buy and Sell Stock III - limited transactions, different DP

Practice

1. You are given a list of daily stock prices and a maximum number of allowed transactions. You want to maximize profit by buying and selling stocks, but you cannot hold more than one stock at a time and must complete each transaction before starting another. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Divide and conquer splitting the price array and merging results

B. Greedy algorithm that buys whenever price is lower than the next day and sells the next day

C. Pure brute force recursion exploring all buy/sell combinations without memoization

D. Dynamic programming using state machines to track buy/sell states for each transaction count

Solution

1. Step 1: Understand problem constraints and limitations of greedy

   The problem limits the number of transactions and requires maximizing profit with buy/sell states, which greedy fails to handle optimally.

2. Step 2: Identify suitable algorithm

   Dynamic programming with state machines tracks holding and not holding states per transaction count, ensuring all possibilities are considered efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Greedy fails on multiple transactions; DP state machines handle all cases [OK]

Hint: DP with states handles transaction limits optimally [OK]

Common Mistakes:

• Assuming greedy always works for stock problems

2. You are given a circular street with houses arranged in a loop, each containing some amount of money. You want to maximize the amount you rob without robbing two adjacent houses, and since the street is circular, the first and last houses are also adjacent. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy algorithm that always picks the house with the maximum money first

B. Dynamic programming by splitting the problem into two linear subproblems excluding either the first or last house

C. Brute force recursion checking all subsets of houses

D. Sorting houses by money and robbing every other house

Solution

1. Step 1: Understand circular adjacency constraint

   The first and last houses cannot both be robbed, so the problem is not a simple linear DP.

2. Step 2: Split into two linear problems

   By considering two cases--rob houses from first to second last, or from second to last--we reduce the circular problem to two linear House Robber problems solvable by DP.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Splitting into two linear DP subproblems handles circular adjacency correctly [OK]

Hint: Split circular problem into two linear DP cases [OK]

Common Mistakes:

• Assuming greedy or sorting works
• Trying to rob first and last house together
• Using brute force without pruning

3. You are given an array where each element represents the maximum jump length from that position. Your goal is to reach the last index in the minimum number of jumps. Which algorithmic approach guarantees finding the minimum number of jumps efficiently?

easy

A. A greedy approach that tracks the furthest reachable index and increments jumps when the current range ends

B. A depth-first search with memoization caching minimum jumps from each position

C. A bottom-up dynamic programming approach that fills a dp array with minimum jumps to each index

D. A brute force recursion exploring all jump paths

Solution

1. Step 1: Understand problem constraints and goal

   The problem requires finding the minimum number of jumps to reach the last index efficiently.

2. Step 2: Evaluate algorithmic approaches

   Brute force recursion explores all paths but is exponential and inefficient. DFS with memoization improves but still can be costly. Bottom-up DP solves the problem in O(n^2) time. The greedy approach runs in O(n) time by tracking the furthest reachable index and incrementing jumps only when the current range ends, guaranteeing the minimum jumps.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Greedy approach is optimal and runs in linear time [OK]

Hint: Greedy tracks furthest reachable and increments jumps at range end [OK]

Common Mistakes:

• Assuming brute force is efficient enough
• Confusing greedy with bottom-up DP
• Thinking DFS with memo is always best

4. Suppose the stock trading problem is modified so that you must pay a transaction fee for each sale. Which of the following changes to the state machine DP solution correctly accounts for the fee while maintaining optimal profit calculation?

hard

A. Add the fee to both buying and selling updates to ensure fee is counted twice

B. Subtract the fee from the buying price when updating holding: holding = max(holding, prev_not_holding - prices[i] - fee)

C. Subtract the fee from the selling price when updating not_holding: not_holding = max(not_holding, holding + prices[i] - fee)

D. Ignore the fee in DP and subtract total fee at the end from final profit

Solution

1. Step 1: Understand fee impact

   The fee applies on each sale, so it should reduce the profit gained when selling.

2. Step 2: Adjust DP transitions

   Subtract fee from the selling transition: not_holding = max(not_holding, holding + prices[i] - fee). Buying price remains unchanged.

3. Step 3: Why other options fail

   Subtracting fee on buying overcharges; adding fee twice double counts; ignoring fee until end breaks DP correctness.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Fee reduces profit only on selling, correctly modeled in not_holding update [OK]

Hint: Fee applies only on selling, subtract from selling transition [OK]

Common Mistakes:

• Subtracting fee on buying instead of selling
• Double counting fee on buy and sell
• Ignoring fee in DP transitions

5. Suppose the problem changes so you can climb 1, 2, or 3 steps at a time. Which modification to the bottom-up DP approach correctly computes the minimum cost to reach the top?

hard

A. Change the recurrence to curr = cost[i] + min(prev1, prev2) and keep the same loop

B. Keep the original code but run the loop until n+1 to cover extra steps

C. Use a greedy approach picking the cheapest next step among 1, 2, or 3 steps

D. Change the recurrence to curr = cost[i] + min(prev1, prev2, prev3) and track three previous states

Solution

1. Step 1: Understand new step options

   With 1, 2, or 3 steps allowed, the cost to reach step i depends on the minimum cost to reach steps i-1, i-2, and i-3.

2. Step 2: Modify DP recurrence and state tracking

   Track three previous states (prev1, prev2, prev3) and compute curr = cost[i] + min(prev1, prev2, prev3) to cover all possibilities.

3. Step 3: Reject incorrect options

   Change the recurrence to curr = cost[i] + min(prev1, prev2) and keep the same loop ignores the third previous step, greedy fails to guarantee global minimum, and extending loop without updating recurrence is incorrect.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   DP recurrence must consider all allowed step sizes [OK]

Hint: Include all allowed previous steps in min calculation [OK]

Common Mistakes:

• Ignoring new step size in recurrence
• Using greedy instead of DP
• Extending loop without recurrence update