LeetCode #309 Medium

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.

dynamic-programmingarraystate-machine

02

Intuition

💡

The tempting shortcut is to track one number, the max profit reachable by day i, and update it greedily. That collapses two different situations into one: whether you are allowed to buy today depends on whether you sold yesterday, and a single running max cannot see that. You need three parallel states per day instead: holding a share, having just sold today, and resting (own nothing, did not just sell). The cooldown rule becomes a single missing transition: rest can only be entered from yesterday's rest or yesterday's sold, and hold can only buy out of rest, never out of a fresh sold. That one forbidden edge is the entire cooldown constraint, encoded structurally instead of checked with an if.

03

Approach

1

Define three rolling states

Keep hold (best profit while currently owning a share), sold (best profit having sold exactly today), and rest (best profit owning nothing and not having sold today). Initialize hold to -prices[0] since day 0's only option is to buy, and sold/rest to 0/-infinity respectively.

2

Transition day by day

Each day, the new hold is the better of keeping yesterday's share or buying today out of yesterday's rest state. The new sold is always yesterday's hold plus today's price, since selling requires having held. The new rest is the better of staying resting or coming off cooldown from yesterday's sold. Compute all three from the previous day's values before overwriting, so nothing reads an already-updated state.

3

Read off the answer

The optimal ending state can never be hold, since an unsold share is profit left on the table. The answer is the maximum of the final sold and rest values, both of which represent ending the timeline owning nothing.

04

Solution & live demo

python

▶1class Solution:
▶2    def maxProfit(self, prices: list[int]) -> int:
▶3        n = len(prices)
▶4        if n < 2:
▶5            return 0
▶6        hold, sold, rest = -prices[0], float('-inf'), 0
▶7        for i in range(1, n):
▶8            new_hold = max(hold, rest - prices[i])
▶9            new_sold = hold + prices[i]
▶10            new_rest = max(rest, sold)
▶11            hold, sold, rest = new_hold, new_sold, new_rest
▶12        return max(sold, rest)

05

Edge cases

Single price / empty array

With fewer than 2 days there is no possible trade, so both sold and rest stay at 0 and the answer is 0.

Prices strictly decreasing

Every buy loses money, so hold never contributes a positive update; sold and rest both settle at 0, correctly reporting no profitable trade exists.

Two-day rise then immediate cooldown-forced wait

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.

Alternating up/down prices

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.

06

Complexity

Time

O(n)

Space

O(1)

Three rolling scalars replace what would otherwise be a 3 x n table.