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
PreviewThe 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…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewUse 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…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
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) |
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
To decide whether to buy the stock on the current day or skip to the next day without buying.
Explore Sell and Cooldown Choices When Holding Stock
To decide whether to sell the stock on the current day or skip to the next day without selling.
Return the Maximum Profit Starting from Day Zero with Buying Allowed
To initiate the recursive DP process from the first day with the ability to buy stock.
3 more steps with full analysis available on Pro.
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.
Full line-by-line criticality + rationale for all 17 lines available on Pro.
Test Your Understanding
Why does the algorithm advance the day index by two after selling instead of one?
See the answer with Pro.
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