Best Time to Buy and Sell Stock with Cooldown
Best Time to Buy and Sell Stock with Cooldown: max profit from unlimited trades where a sell forces one cooldown day before the next buy.
- 1 <= prices.length <= 5000
- 0 <= prices[i] <= 1000
Intuition
Best time to buy and sell stock with cooldown allows unlimited transactions, but after selling you must wait one full day before buying again. That single restriction breaks the greedy solution that works for the unrestricted version.
With a cooldown, taking every price rise is no longer safe. Selling to capture a small gain can block a much larger one the following day, so the decision at each step depends on what happened previously.
That dependency is what makes this a DP problem, and the states follow from asking what actually distinguishes one day from another. Owning a share is one situation. Not owning one splits in two, because being free to buy differs from being blocked by the cooldown:
- Three states are needed: holding a share, resting and free to buy, and cooling down after a sale.
The transitions then write themselves. hold comes from continuing to hold, or from buying while in the rest state — never while cooling down, which is exactly where the restriction lives. sold comes only from selling a held share. rest comes from continuing to rest, or from yesterday's sold, since one day of cooldown has now elapsed.
The reason hold reads from rest and never from sold is the cooldown rule. There is no separate check for it anywhere in the code.
Initial values matter: hold starts at −prices[0], while sold and rest start at 0.
The answer is max(sold, rest) on the final day — ending while holding is never optimal, since that share could have been sold or never bought.
Three states per day — holding, just sold, resting — with transitions between them. The cooldown is expressed structurally: you can only buy from rest, and sold must pass through rest before buying again. State machines handle constraints that a single running variable can't.
Approach
Before reading on: price up what the direct approach costs here, then ask what a single cell should mean, and which earlier cells it needs. Aim for O(n) time and O(1) space.
See why greedy fails here
With a cooldown, capturing a small rise can block a larger one the next day. The decision now depends on history, which is what forces a DP rather than a per-day comparison.
Define three states
Holding a share, resting and free to buy, and cooling down after a sale. Not owning a share splits in two, because being free to buy differs from being blocked.
Transition into hold
hold = max(hold, rest - price) — keep the share, or buy while rested. Reading from rest and never from sold is the cooldown rule itself, with no separate check anywhere.
Transition into sold
sold = hold + price — the only way to reach this state is by selling a share held yesterday. It is not a maximum, since there is exactly one route in.
Transition into rest
rest = max(rest, prevSold) — stay rested, or emerge from yesterday's sale now that one day has passed. This is where the cooldown expires.
Use yesterday's values
Every transition reads the previous day's states. Update from saved copies, or a value overwritten earlier in the same iteration corrupts the ones after it.
Return the best non-holding state
The answer is max(sold, rest) on the last day. Ending while holding is never optimal — that share could have been sold, or never bought.
Cost of the scan
One pass updating three variables gives O(n) time and O(1) space, since only the previous day's states are ever needed.
Solution & live demo
Common pitfalls
Updating the states sequentially
hold = max(hold, rest - prices[i]) sold = hold + prices[i]
new_hold = max(hold, rest - prices[i]) new_sold = hold + prices[i] ... hold, sold, rest = new_hold, new_sold, new_rest
The second line would use today's hold rather than yesterday's, allowing a buy and sell on the same day. All three transitions must read the previous day's values.
Buying from the sold state
new_hold = max(hold, sold - prices[i])
new_hold = max(hold, rest - prices[i])
That's precisely the cooldown violation — buying the day after selling. Routing purchases through rest forces the mandatory idle day between a sale and the next purchase.
Returning hold in the final answer
return max(hold, sold, rest)
return max(sold, rest)
Ending while still holding a share means the money is tied up in stock, not realised as profit. Only the two cash states are valid endings.
Edge cases
With fewer than 2 days there is no possible trade, so both sold and rest stay at 0 and the answer is 0.
Every buy loses money, so hold never contributes a positive update; sold and rest both settle at 0, correctly reporting no profitable trade exists.
After a sell, the very next buy attempt out of sold is structurally impossible since buys only draw from rest, which naturally enforces the one-day gap.
The running max in each state means a locally bad day never destroys a previously found good state; hold, sold, and rest each just keep their best value seen so far.