Problem Statement

Best Time to Buy and Sell Stock with Cooldown

You get an array called prices, where prices[i] is the cost of one share of a stock on day i. You want to make the most money you can by buying low and selling high. You can buy and sell as many times as you want, but there are two rules. First, you can only own one share at a time, so you must sell before you buy again. Second, the day right after you sell, you have to rest, you cannot buy. That resting day is called a cooldown. The trick we use is a state machine, which just means we track which of a few possible "situations" you are in each day, and the best profit you could have in each one. Here we use three situations: you are holding a share, you just sold a share, or you are resting and free to buy.

mediumDynamic ProgrammingDynamic ProgrammingTime: O(n) · Space: O(1)

Signals to notice

buy/sell stock with cooldown after sellingstate machine: hold/sold/cooldowncan't buy immediately after sell

Brute force first

Try all buy/sell/cooldown sequences. Three choices at each day. That instinct is useful because it follows the prompt literally, but it usually keeps revisiting work the problem is begging you to organize.

The key insight

State DP: track three states per day — hold (own stock), sold (just sold), cooldown (resting). Transitions: hold = max(prevHold, prevCooldown - price), sold = prevHold + price, cooldown = max(prevCooldown, prevSold). Instead of recomputing the world every time, you preserve just enough context to let the next decision become obvious.

Trace it on `prices=[1,2,3,0,2]`

init day0 (price=1): hold=-1, sold=0, rest=0
i=1 (price=2): hold=max(-1, 0-2)=-1 | sold=-1+2=1 | rest=max(0,0)=0
i=2 (price=3): hold=max(-1, 0-3)=-1 | sold=-1+3=2 | rest=max(0,1)=1
i=3 (price=0): hold=max(-1, 1-0)=1 | sold=-1+0=-1 | rest=max(1,2)=2
i=4 (price=2): hold=max(1, 2-2)=1 | sold=1+2=3 | rest=max(2,-1)=2
end: not holding -> return max(sold=3, rest=2) = 3

What must stay true

Three states capture all possibilities. The cooldown state enforces the one-day waiting period after selling. Each state depends only on the previous day's states. As long as that statement keeps holding, you can trust the steps built on top of it.

Shape of the loop

hold = -prices[0]; sold = 0; rest = 0
for i in 1..n-1:
    pHold, pSold, pRest = hold, sold, rest
    hold = max(pHold, pRest - prices[i])   # keep / buy after cooldown
    sold = pHold + prices[i]               # sell today
    rest = max(pRest, pSold)               # stay resting / enter cooldown
return max(sold, rest)

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Forgetting that you can't buy the day after selling — that's what the cooldown state enforces. Without it, you'd accidentally allow immediate re-buying. Most mistakes here are not about syntax; they come from losing track of what your state, pointer, or structure is supposed to mean.

Dynamic Programming Pattern