Best Time - Cooldown

📋

Problem

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?

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

Edge cases: Single day prices → profit is 0 because no transactions possibleAll prices are the same → profit is 0 because no gain from transactionsStrictly decreasing prices → profit is 0 because no profitable transactions

</>

IDE

def maxProfit(prices: list[int]) -> int:public int maxProfit(int[] prices)int maxProfit(vector<int> &prices)function maxProfit(prices)

def maxProfit(prices):
    # Write your solution here
    pass

class Solution {
    public int maxProfit(int[] prices) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int maxProfit(vector<int> &prices) {
    // Write your solution here
    return 0;
}

function maxProfit(prices) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Always returning 0 by skipping all transactions, ignoring profitable trades.✅ Implement DP states to track holding and cooldown; do not skip profitable transactions.

Wrong: 5Ignoring cooldown day after sell, allowing immediate buy next day.✅ Add cooldown state after sell to prevent buying on next day.

Wrong: Negative or incorrect profitAllowing transactions that lose money or incorrect state updates.✅ Ensure max profit never decreases; only buy if profitable and update states correctly.

Wrong: Timeout or no outputUsing brute force recursion without memoization causing exponential time.✅ Use DP with memoization or bottom-up approach to achieve O(n) time.

✓

Test Cases

Focus on handling empty and minimal inputs correctly.

Test your solution against tricky cases with multiple cooldowns and price patterns.

Ensure your solution runs in linear time to handle large inputs efficiently.

t1_01basic

Input{"prices":[1,2,3,0,2]}

Expected3

⏱ Performance - must finish in 2000ms

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

💡 Think about states: holding stock, not holding and in cooldown, or free to buy.

💡 Use dynamic programming with states to track max profit each day.

💡 Transition: sell leads to cooldown next day; buy only allowed if not in cooldown.

Why it failed: Incorrect profit means state transitions are wrong; fix by ensuring cooldown day after sell disallows buying.

✓ Correctly handles cooldown and state transitions.

t1_02basic

Input{"prices":[1,2,4]}

Expected3

⏱ Performance - must finish in 2000ms

Buy day 0, sell day 2 for profit 3; no cooldown needed as only one transaction.

💡 Check if your solution handles simple increasing prices correctly.

💡 Confirm that buying early and selling later yields max profit.

💡 Ensure cooldown does not prevent profitable single transactions.

Why it failed: Failing this means cooldown logic blocks valid transactions; fix by allowing buy if not in cooldown.

✓ Handles simple increasing prices and cooldown correctly.

t2_01edge

Input{"prices":[]}

Expected0

⏱ Performance - must finish in 2000ms

Empty prices array means no transactions possible, profit is 0.

💡 Consider what happens if there are no days to trade.

💡 Your code should handle empty input gracefully.

💡 Return 0 immediately if prices list is empty.

Why it failed: Code crashes or returns non-zero on empty input; fix by adding base case for empty prices.

✓ Correctly returns 0 for empty input.

t2_02edge

Input{"prices":[5]}

Expected0

⏱ Performance - must finish in 2000ms

Single day means no sell possible, profit is 0.

💡 With only one day, no transactions can be completed.

💡 Check base cases for small input sizes.

💡 Return 0 if prices length is 1.

Why it failed: Returns non-zero profit for single day; fix by ensuring at least one buy and sell needed.

✓ Correctly returns 0 for single day input.

t2_03edge

Input{"prices":[3,3,3,3,3]}

Expected0

⏱ Performance - must finish in 2000ms

All prices equal means no profitable transactions, profit is 0.

💡 Check if your solution avoids buying and selling at same price.

💡 Profit should never be negative or zero if no gain.

💡 Ensure cooldown logic does not force unnecessary transactions.

Why it failed: Returns positive profit on flat prices; fix by preventing buy/sell when no price gain.

✓ Correctly returns 0 when prices do not increase.

t3_01corner

Input{"prices":[5,4,3,2,1]}

Expected0

⏱ Performance - must finish in 2000ms

Strictly decreasing prices mean no profitable transactions, profit is 0.

💡 Check if your solution avoids buying when prices only go down.

💡 Confirm no forced transactions that cause losses.

💡 Ensure max profit never negative; return 0 if no profit possible.

Why it failed: Returns negative or positive profit on decreasing prices; fix by disallowing transactions that lose money.

✓ Correctly returns 0 for strictly decreasing prices.

t3_02corner

Input{"prices":[1,2,3,0,2,1,4]}

Expected5

⏱ Performance - must finish in 2000ms

Buy day 0 sell day 2 (profit 2), cooldown day 3, buy day 4 sell day 6 (profit 4), total 6.

💡 Test if your solution correctly handles multiple cooldowns and transactions.

💡 Check state transitions carefully for cooldown days after each sell.

💡 Ensure dp states track cooldown and holding correctly over multiple transactions.

Why it failed: Fails to maximize profit with multiple cooldowns; fix by correctly updating states after each sell.

✓ Handles multiple transactions with cooldown correctly.

t3_03corner

Input{"prices":[1,2,3,0,2,0,1,3]}

Expected5

⏱ Performance - must finish in 2000ms

Buy day 0 sell day 2 (profit 2), cooldown day 3, buy day 4 sell day 7 (profit 5), total 7.

💡 Beware greedy approaches that buy/sell every increase without cooldown.

💡 Check that cooldown days are enforced after each sell.

💡 Use state machine DP to track holding, cooldown, and free states.

Why it failed: Greedy approach fails here by ignoring cooldown; fix by implementing state machine DP with cooldown state.

✓ Correctly handles cooldown and multiple transactions avoiding greedy traps.

t4_01performance

Input{"prices":[10000,9999,9998,9997,9996,9995,9994,9993,9992,9991,9990,9989,9988,9987,9986,9985,9984,9983,9982,9981,9980,9979,9978,9977,9976,9975,9974,9973,9972,9971,9970,9969,9968,9967,9966,9965,9964,9963,9962,9961,9960,9959,9958,9957,9956,9955,9954,9953,9952,9951,9950,9949,9948,9947,9946,9945,9944,9943,9942,9941,9940,9939,9938,9937,9936,9935,9934,9933,9932,9931,9930,9929,9928,9927,9926,9925,9924,9923,9922,9921,9920,9919,9918,9917,9916,9915,9914,9913,9912,9911,9910,9909,9908,9907,9906,9905,9904,9903,9902,9901]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, prices strictly decreasing, O(n) DP must complete within 2 seconds.

💡 Brute force exponential solutions will time out here.

💡 Use O(n) DP with state machine to solve efficiently.

💡 Optimize space by tracking only previous states.

Why it failed: TLE indicates exponential or non-linear complexity; fix by implementing O(n) DP with states.

✓ Solution runs in O(n) time confirming efficient DP implementation.

Practice

1. You are given an array of stock prices where you can complete at most two transactions (buy-sell pairs). Which algorithmic approach guarantees finding the maximum profit efficiently?

easy

A. Dynamic programming with state machine tracking transactions and holding states

B. Greedy approach that picks local minima and maxima twice

C. Brute force checking all pairs of buy and sell days twice

D. Divide and conquer splitting the array into two halves and combining results

Solution

1. Step 1: Understand problem constraints

   At most two transactions means we must track states for 0, 1, or 2 completed transactions and whether we hold stock or not.

2. Step 2: Identify suitable algorithm

   Greedy and divide-and-conquer fail to consider overlapping subproblems and state transitions correctly. Brute force is correct but inefficient. DP with state machines efficiently tracks profits per transaction count and holding state.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP with states is standard for multi-transaction stock problems [OK]

Hint: Track transactions and holding states with DP [OK]

Common Mistakes:

• Assuming greedy picks always yield global optimum
• Using brute force without pruning

2. You are given a list of non-negative integers representing the amount of money in each house along a street. You want to maximize the total amount you can rob tonight without robbing two adjacent houses. Which algorithmic approach guarantees finding the optimal solution efficiently?

easy

A. Dynamic programming that considers robbing or skipping each house to maximize total

B. A greedy algorithm that always picks the house with the maximum amount next

C. Sorting the houses by amount and picking the top half

D. Depth-first search exploring all subsets of houses

Solution

1. Step 1: Understand problem constraints

   The problem requires maximizing sum without robbing adjacent houses, which is a classic overlapping subproblems scenario.

2. Step 2: Identify suitable algorithm

   Dynamic programming fits because it explores choices at each house (rob or skip) and uses previous results to build optimal solution.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Greedy fails on cases like [2,7,9,3,1], DP finds max 12 [OK]

Hint: DP handles overlapping subproblems and optimal substructure [OK]

Common Mistakes:

• Greedy approach fails on non-adjacent constraints

3. Consider the following Python code implementing the House Robber problem using space-optimized DP. What is the value of prev1 after the third iteration of the loop when input is [2, 1, 4]?

def rob(nums):
    prev1, prev2 = 0, 0
    for num in nums:
        temp = prev1
        prev1 = max(prev1, prev2 + num)
        prev2 = temp
    return prev1

easy

A. 6

B. 4

C. 5

D. 7

Solution

1. Step 1: Trace iterations

   Iteration 1 (num=2): prev1= max(0,0+2)=2, prev2=0 Iteration 2 (num=1): prev1= max(2,0+1)=2, prev2=2 Iteration 3 (num=4): prev1= max(2,2+4)=6, prev2=2

2. Step 2: Identify value after third iteration

   After third iteration, prev1=6

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Manual calculation confirms prev1=6 after third iteration [OK]

Hint: Track prev1 and prev2 updates carefully each iteration [OK]

Common Mistakes:

• Confusing prev1 and prev2 updates
• Off-by-one iteration counting

4. What is the time and space complexity of the optimal space-optimized dynamic programming solution for the Best Time -- Transaction Fee problem, given n prices?

medium

A. Time: O(n), Space: O(1) by tracking only two states per iteration

B. Time: O(n²), Space: O(n) due to nested loops and DP table

C. Time: O(n), Space: O(n) because of memoization cache or DP array

D. Time: O(n log n), Space: O(1) due to sorting and constant state variables

Solution

1. Step 1: Identify time complexity

   The algorithm iterates once over the prices array, performing constant time operations per element -> O(n).

2. Step 2: Identify space complexity

   Only two variables (cash and hold) are maintained and updated each iteration -> O(1) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass and constant state variables confirm O(n) time and O(1) space [OK]

Hint: Only two states tracked, no DP table needed [OK]

Common Mistakes:

• Confusing recursion stack space with DP space
• Assuming DP table stored for all days

5. What is the time complexity of the top-down memoized recursive solution for the House Robber problem with input size n, and why might some candidates mistakenly think it is exponential?

medium

A. O(n^2) due to overlapping subproblems recomputed multiple times

B. O(2^n) because each call branches into two recursive calls

C. O(n) because memoization ensures each index is computed once

D. O(n log n) because recursion depth is logarithmic

Solution

1. Step 1: Analyze recursion with memoization

   Memoization caches results for each index i, so robFrom(i) is computed once per i.

2. Step 2: Determine total calls and complexity

   Since i ranges from 0 to n-1, total calls are O(n), each O(1) work -> O(n) time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Without memoization, calls explode exponentially; memoization reduces to linear [OK]

Hint: Memoization reduces exponential calls to linear by caching [OK]

Common Mistakes:

• Assuming recursion always exponential
• Ignoring memoization effect