Best Time to Buy and Sell Stock with Cooldown
Problem
Given an array prices where prices[i] is the price of a given stock on the ith day, return the maximum profit you can achieve with as many transactions as you like, but after you sell a stock, you cannot buy stock on the next day (cooldown one day).
- 1 ≤ prices.length ≤ 5000
- 0 ≤ prices[i] ≤ 1000
Example
prices = [1,2,3,0,2]3The optimal sequence is: buy on day 0 (price=1), sell on day 1 (price=2), cooldown on day 2, buy on day 3 (price=0), sell on day 4 (price=2). The total profit is (2-1) + (2-0) = 3. The algorithm explores states day-by-day, deciding whether to buy, sell, or cooldown, while respecting the cooldown constraint by skipping the day after a sell.
Approach
Straightforward Solution
A brute-force approach tries all possible sequences of buy, sell, and cooldown actions, exploring an exponential number of states, which is computationally infeasible for large inputs.
Core Observation
The problem models a sequence of decisions with state-dependent constraints: after selling, a cooldown day is required before buying again. This creates overlapping subproblems with state transitions that depend on both the current day and whether the algorithm is allowed to buy or must wait.
Path to Optimal
The key recognition signals are 'maximum profit', 'multiple transactions allowed', and 'cooldown after sell'. These indicate Dynamic Programming because the problem breaks down into subproblems defined by day index and holding state. The cooldown constraint requires skipping a day after selling, which can be modeled by advancing the day index by two after a sell. Memoization or tabulation avoids redundant computations by caching results for each state.
Optimal Approach
Use a top-down DP with memoization. Define a function dp(i, buying) that returns the maximum profit starting from day i with the ability to buy if buying is True, or must sell if buying is False. When buying, choose between buying the stock (and subtracting price) or skipping (cooldown). When selling, choose between selling the stock (and adding price, then skipping the next day due to cooldown) or skipping. Memoize results to ensure O(n) time complexity. This approach correctly models the cooldown by advancing the day index by two after selling.
Time
O(n)
Each day and state (buying or selling) is computed once and cached. There are 2 states per day and n days, resulting in O(2n) = O(n) time complexity.
Space
O(n)
The memoization dictionary stores results for each day and buying state, totaling O(2n) = O(n) auxiliary space. This space is necessary to avoid redundant computations.
Pattern Spotlight
Dynamic Programming (State Machine with Cooldown)
Model the problem as a state machine with explicit states for 'can buy' and 'can sell', and incorporate cooldown by skipping days after selling; memoize results to avoid recomputation and capture the optimal profit for each state.
Solution
| 1 | class Solution:
|
| 2 | def maxProfit(self, prices: list[int]) -> int:
|
| 3 | memo = {}
|
| 4 |
|
| 5 | def dp(i, buying):
|
| 6 | if i >= len(prices):
|
| 7 | return 0
|
| 8 | if (i, buying) in memo:
|
| 9 | return memo[(i, buying)]
|
| 10 |
|
| 11 | if buying:
|
| 12 | buy = dp(i + 1, False) - prices[i]
|
| 13 | cooldown = dp(i + 1, True)
|
| 14 | result = max(buy, cooldown)
|
| 15 | else:
|
| 16 | sell = dp(i + 2, True) + prices[i]
|
| 17 | cooldown = dp(i + 1, False)
|
| 18 | result = max(sell, cooldown)
|
| 19 |
|
| 20 | memo[(i, buying)] = result
|
| 21 | return result
|
| 22 |
|
| 23 | return dp(0, True) |
| 1 | import java.util.HashMap; |
| 2 | import java.util.Map; |
| 3 | |
| 4 | public class Solution { |
| 5 | public int maxProfit(int[] prices) { |
| 6 | Map<String, Integer> memo = new HashMap<>(); |
| 7 | |
| 8 | return dp(0, true, prices, memo); |
| 9 | } |
| 10 | |
| 11 | private int dp(int i, boolean buying, int[] prices, Map<String, Integer> memo) { |
| 12 | if (i >= prices.length) { |
| 13 | return 0; |
| 14 | } |
| 15 | String key = i + "," + buying; |
| 16 | if (memo.containsKey(key)) { |
| 17 | return memo.get(key); |
| 18 | } |
| 19 | |
| 20 | int result; |
| 21 | if (buying) { |
| 22 | int buy = dp(i + 1, false, prices, memo) - prices[i]; |
| 23 | int cooldown = dp(i + 1, true, prices, memo); |
| 24 | result = Math.max(buy, cooldown); |
| 25 | } else { |
| 26 | int sell = dp(i + 2, true, prices, memo) + prices[i]; |
| 27 | int cooldown = dp(i + 1, false, prices, memo); |
| 28 | result = Math.max(sell, cooldown); |
| 29 | } |
| 30 | |
| 31 | memo.put(key, result); |
| 32 | return result; |
| 33 | } |
| 34 | } |
| 1 | #include <vector> |
| 2 | #include <unordered_map> |
| 3 | #include <string> |
| 4 | #include <algorithm> |
| 5 | |
| 6 | using namespace std; |
| 7 | |
| 8 | class Solution { |
| 9 | public: |
| 10 | int maxProfit(vector<int>& prices) { |
| 11 | return dp(0, true, prices); |
| 12 | } |
| 13 | |
| 14 | private: |
| 15 | unordered_map<string, int> memo; |
| 16 | |
| 17 | int dp(int i, bool buying, vector<int>& prices) { |
| 18 | if (i >= (int)prices.size()) { |
| 19 | return 0; |
| 20 | } |
| 21 | string key = to_string(i) + "," + (buying ? "1" : "0"); |
| 22 | if (memo.find(key) != memo.end()) { |
| 23 | return memo[key]; |
| 24 | } |
| 25 | |
| 26 | int result; |
| 27 | if (buying) { |
| 28 | int buy = dp(i + 1, false, prices) - prices[i]; |
| 29 | int cooldown = dp(i + 1, true, prices); |
| 30 | result = max(buy, cooldown); |
| 31 | } else { |
| 32 | int sell = dp(i + 2, true, prices) + prices[i]; |
| 33 | int cooldown = dp(i + 1, false, prices); |
| 34 | result = max(sell, cooldown); |
| 35 | } |
| 36 | |
| 37 | memo[key] = result; |
| 38 | return result; |
| 39 | } |
| 40 | }; |
| 1 | var maxProfit = function(prices) { |
| 2 | const memo = new Map(); |
| 3 | |
| 4 | function dp(i, buying) { |
| 5 | if (i >= prices.length) { |
| 6 | return 0; |
| 7 | } |
| 8 | const key = i + ',' + buying; |
| 9 | if (memo.has(key)) { |
| 10 | return memo.get(key); |
| 11 | } |
| 12 | |
| 13 | let result; |
| 14 | if (buying) { |
| 15 | const buy = dp(i + 1, false) - prices[i]; |
| 16 | const cooldown = dp(i + 1, true); |
| 17 | result = Math.max(buy, cooldown); |
| 18 | } else { |
| 19 | const sell = dp(i + 2, true) + prices[i]; |
| 20 | const cooldown = dp(i + 1, false); |
| 21 | result = Math.max(sell, cooldown); |
| 22 | } |
| 23 | |
| 24 | memo.set(key, result); |
| 25 | return result; |
| 26 | } |
| 27 | |
| 28 | return dp(0, true); |
| 29 | }; |
Step-by-Step Solution
Memoize Recursive State Results to Avoid Redundant Computation
| 3 | memo = {}
|
| 5 | def dp(i, buying):
|
| 6 | if i >= len(prices):
|
| 7 | return 0
|
| 8 | if (i, buying) in memo:
|
| 9 | return memo[(i, buying)]
|
| 20 | memo[(i, buying)] = result
|
| 21 | return result
|
Objective
To store computed maximum profits for each day and buying state to prevent exponential recomputation.
Key Insight
Memoization transforms the naive exponential recursion into a linear-time solution by caching results for each unique state defined by the current day and whether the algorithm is allowed to buy or must sell. This ensures each state is solved once, enabling efficient reuse of subproblem solutions.
Interview Quick-Check
Core Logic
Memoization caches results keyed by (day, buying) state, collapsing exponential recursion into O(n) time.
State & Boundaries
The base case returns 0 when the day index exceeds the last day, signaling no further profit.
Common Pitfalls & Bugs
Forgetting to memoize leads to exponential time due to repeated state evaluations.
Explore Buy and Cooldown Choices When Allowed to Buy
| 11 | if buying:
|
| 12 | buy = dp(i + 1, False) - prices[i]
|
| 13 | cooldown = dp(i + 1, True)
|
| 14 | result = max(buy, cooldown)
|
Objective
To decide whether to buy the stock on the current day or skip to the next day without buying.
Key Insight
When allowed to buy, the algorithm compares two options: buying the stock (which reduces profit by the current price and transitions to the selling state) or skipping the day (cooldown). This choice models the decision to invest now or wait for a better opportunity, capturing the trade-off between immediate cost and future gain.
Interview Quick-Check
Core Logic
The algorithm calculates max profit by choosing between buying today (subtract price and switch to selling state) or skipping today (remain in buying state).
State & Boundaries
Buying transitions the state to 'not buying' (selling) for the next day.
Common Pitfalls & Bugs
Mixing up the buying and selling states or forgetting to subtract the price when buying leads to incorrect profit calculations.
Explore Sell and Cooldown Choices When Holding Stock
| 15 | else:
|
| 16 | sell = dp(i + 2, True) + prices[i]
|
| 17 | cooldown = dp(i + 1, False)
|
| 18 | result = max(sell, cooldown)
|
Objective
To decide whether to sell the stock on the current day or skip to the next day without selling.
Key Insight
When holding stock, the algorithm chooses between selling today (which adds the current price to profit and enforces a cooldown by skipping the next day) or skipping today (cooldown without selling). This models the trade-off between realizing profit now and waiting for a potentially better selling price later, while respecting the cooldown constraint.
Interview Quick-Check
Core Logic
The algorithm calculates max profit by choosing between selling today (add price and skip next day) or skipping today (remain holding).
State & Boundaries
Selling transitions the state back to 'buying' after skipping one day due to cooldown.
Common Pitfalls & Bugs
Failing to skip the cooldown day after selling or incorrectly advancing the day index leads to invalid solutions.
Return the Maximum Profit Starting from Day Zero with Buying Allowed
| 23 | return dp(0, True) |
Objective
To initiate the recursive DP process from the first day with the ability to buy stock.
Key Insight
Starting from day zero with buying allowed models the initial state of the problem where no stock is held and the algorithm can choose to buy or skip. This call triggers the entire memoized recursion that explores all valid sequences of buy, sell, and cooldown actions to find the maximum profit.
Interview Quick-Check
Core Logic
The initial call dp(0, True) represents starting fresh with no stock and the option to buy.
Complexity
This single call initiates the O(n) memoized recursion that efficiently computes the optimal profit.
Line Analysis
This solution has 8 Critical lines interviewers watch for.
if (i, buying) in memo:Check if the current state has been computed before.
This lookup prevents redundant calculations by returning cached results, critical for efficiency.
return memo[(i, buying)]Return the cached result for the current state.
Returning memoized results collapses the recursion tree, ensuring each state is solved once.
sell = dp(i + 2, True) + prices[i]Calculate profit if selling today: add price and recurse skipping next day due to cooldown.
Adding the price models profit realization, and skipping the next day enforces the cooldown constraint.
memo = {}Initialize a memoization dictionary to cache results for states.
Memoization is essential to avoid exponential recomputation by storing results for each (day, buying) state, enabling O(n) time complexity.
buy = dp(i + 1, False) - prices[i]Calculate profit if buying today: subtract price and recurse to selling state next day.
Subtracting the price models the cost of buying, and transitioning to selling state captures the next decision context.
result = max(buy, cooldown)Select the maximum profit between buying and skipping today.
Taking the max ensures the algorithm chooses the optimal action at this state.
result = max(sell, cooldown)Select the maximum profit between selling and skipping today.
Taking the max ensures the algorithm chooses the optimal action at this state.
memo[(i, buying)] = resultCache the computed maximum profit for the current state.
Memoizing the result prevents redundant computations and enables efficient recursion.
def dp(i, buying):Define the recursive DP function with parameters day index and buying state.
This function models the problem as a state machine, capturing the decision context at each day and whether buying is allowed.
if buying:Check if the algorithm is allowed to buy on this day.
This conditional branches the logic between buying and selling states, defining the state machine's behavior.
cooldown = dp(i + 1, True)Calculate profit if skipping buying today (cooldown).
Skipping preserves the buying state for the next day, modeling the choice to wait for a better opportunity.
else:Handle the case when holding stock and must decide to sell or skip.
This branch models the selling state, where the algorithm can realize profit or wait.
cooldown = dp(i + 1, False)Calculate profit if skipping selling today (cooldown).
Skipping preserves the selling state for the next day, modeling the choice to wait for a better selling price.
return resultReturn the cached maximum profit for the current state.
Returning the memoized value completes the recursion step and propagates the optimal profit upward.
return dp(0, True)Start the DP recursion from day zero with buying allowed.
This initial call models the problem's starting condition and triggers the entire memoized exploration of all valid trading sequences.
if i >= len(prices):Check if the day index exceeds the last day.
This base case terminates recursion when no more days remain, returning zero profit as no further transactions are possible.
return 0Return zero profit for base case of no remaining days.
Returning zero here correctly signals that no profit can be made beyond the last day, anchoring the recursion.
Test Your Understanding
Why does the algorithm advance the day index by two after selling instead of one?
Because the cooldown constraint forbids buying on the day immediately after selling, the algorithm must skip that day, effectively advancing two days after a sell to respect the cooldown period.
Related Problems
Dynamic Programming pattern
Don't just read it. Drill it.
Reconstruct Best Time to Buy and Sell Stock with Cooldown from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Best Time to Buy and Sell Stock with Cooldown drill