Best Time to Buy and Sell Stock with Cooldown II solution and explanation
The problem
You are given an integer array prices of length n, where prices[i] is the price of a stock on day i.
You are also given an integer cooldown and an integer array costs of length n. The value costs[k] is the total holding fee for a transaction in which the stock is held for exactly k days.
You may perform any number of transactions, including zero, subject to the following rules:
- You may hold at most one share at a time. You must sell your current share before buying another.
- If you sell on day
j, the earliest day you may buy again isj + cooldown + 1. - If you buy on day
iand sell on dayj, the holding duration isj - idays. You pay the feecosts[j - i]once for that transaction.
The profit from buying on day i and selling on day j is prices[j] - prices[i] - costs[j - i].
Return the maximum total profit you can achieve. If no profitable transactions are possible, return 0.
Example 1:
Input: prices = [1,5,3], cooldown = 1, costs = [2,0,1]
Output: 4
Explanation:
The optimal strategy is:
- Buy on day 0 at
prices[0] = 1. - Sell on day 1 at
prices[1] = 5. The holding duration is 1 day, so the holding cost iscosts[1] = 0. - Therefore, the profit from this transaction is
5 - 1 - 0 = 4. - After selling,
cooldown = 1prevents buying any stock on day 2, so no further transactions are possible. - Maximum profit achievable is 4.
Example 2:
Input: prices = [1,2,5], cooldown = 0, costs = [0,2,1]
Output: 3
Explanation:
The optimal strategy is:
- Buy on day 0 at
prices[0] = 1. - Sell on day 2 at
prices[2] = 5. The holding duration is 2 days, so the holding cost iscosts[2] = 1. - Therefore, the profit from this transaction is
5 - 1 - 1 = 3. - No further transactions improve the profit. Maximum profit achievable is 3.
Example 3:
Input: prices = [4,1,7], cooldown = 2, costs = [3,0,1]
Output: 6
Explanation:
The optimal strategy is:
- Buy on day 1 at
prices[1] = 1. - Sell on day 2 at
prices[2] = 7. The holding duration is 1 day, so the holding cost iscosts[1] = 0. - Profit from this transaction =
7 - 1 - 0 = 6. - No further transactions are possible. Maximum profit achievable = 6.
Example 4:
Input: prices = [3,1,4], cooldown = 0, costs = [2,1,0]
Output: 2
Explanation:
The optimal strategy is:
- Buy on day 1 at
prices[1] = 1. - Sell on day 2 at
prices[2] = 4. The holding duration is 1 day, so the holding cost iscosts[1] = 1. - Therefore, the profit from this transaction is
4 - 1 - 1 = 2. - No further transactions improve the profit. Maximum profit achievable is 2.
Constraints:
1 <= n == prices.length <= 15001 <= prices[i] <= 1050 <= cooldown <= n - 1costs.length == n0 <= costs[i] <= 105
Approach overview
Problem Overview: You get an array of daily prices. You can hold at most one share at a time and make unlimited buy-sell trades, but after every sell you must skip the next day before buying again. Return the maximum profit.
Approach 1: Recursion (Exponential)
At each day, branch on three choices: buy, sell, or rest. Track whether you hold a share and whether you are in cooldown. Each branch recurses on the next day. The branching is what makes this slow, since every day can split into multiple paths and the same subproblems get recomputed many times. Time is O(2^n) and space is O(n) for the recursion stack. Use it only to confirm the state transitions before optimizing.
Approach 2: Memoized DP on (day, holding) (O(n) time, O(n) space)
Cache the result of each state so every (day, holding) pair is computed once. The key observation is that the future depends only on the current day and whether you hold a share. Cooldown is handled by jumping to day i + 2 after a sell. This gives O(n) time and O(n) space for the memo table and stack. It is the cleanest way to reason about the problem, and it maps directly to a top-down dynamic programming solution.
Approach 3: Three-State Iterative DP (O(n) time, O(1) space)
Track three values for each day: hold (you own a share), sold (you sold today and are cooling down), and rest (you own nothing and are free to buy). Update them in a single pass over the array. Set hold = max(hold, rest - price), sold = hold + price, and rest = max(rest, sold_prev). Each day uses only the previous day's values, so you need just three variables. Time is O(n) and space is O(1). This is the version you should write in an interview.
Recommended for interviews: Interviewers expect you to start with the recursive or memoized state definition, then compress it to the three-state iteration. The brute force shows you understand the choices. The O(1) state machine shows you can spot the dependency structure and reduce the space. Explain the cooldown transition clearly, since most bugs come from getting the rest state wrong. This problem also builds on the greedy intuition of buying low and selling high, but the cooldown rule means greedy alone fails.
The written solution for this problem is still being prepared. Try it yourself in the meantime.
Try solving it yourselfComplexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursion (brute force) | O(2^n) | O(n) | Validating state transitions only |
| Memoized DP | O(n) | O(n) | Clear top-down reasoning |
| Three-state iterative DP | O(n) | O(1) | General case and interviews |
Frequently asked questions
Best Time to Buy and Sell Stock with Cooldown II Python solution?
Initialize hold to negative infinity, sold to 0, and rest to 0. For each price, set new_hold to max(hold, rest - price), new_sold to hold + price, and new_rest to max(rest, sold). Update the three variables and return max(sold, rest) after the loop.
Is Best Time to Buy and Sell Stock with Cooldown II easy or hard?
It is a medium-difficulty problem with an acceptance rate of about 59.4%. The brute force is straightforward, but getting the cooldown transition right in the O(1) state machine is where most candidates struggle.
How to solve Best Time to Buy and Sell Stock with Cooldown II in O(n)?
Keep three running values: hold for the best profit while owning a share, sold for the profit on the day you just sold, and rest for the best profit while owning nothing and free to buy. On each price, update hold from rest minus the price, set sold to hold plus the price, and set rest to the larger of the old rest and the previous sold value.
What is the best approach for Best Time to Buy and Sell Stock with Cooldown II?
The best approach is a three-state iterative dynamic programming solution that tracks hold, sold, and rest values for each day. It runs in O(n) time and O(1) space. Each day depends only on the previous day's states, so no array is needed.
What data structure is used in Best Time to Buy and Sell Stock with Cooldown II?
The optimal solution uses only a few integer variables and no extra data structure. The memoized version uses a hash map or array keyed by day and holding state. The input is a plain array of prices.
What is the time complexity of Best Time to Buy and Sell Stock with Cooldown II?
The optimal solution runs in O(n) time, where n is the number of prices, because it makes one pass over the array. The naive recursive version runs in O(2^n) time because each day branches into buy, sell, or rest choices.
Is Best Time to Buy and Sell Stock with Cooldown II asked at Google, Amazon, or Meta?
This problem is tagged as General on FleetCode, so it is not linked to a specific company in our data. It is a common dynamic programming question in interview prep, and the state machine pattern appears across many stock trading variants.