4.24.3 — Best Time to Buy and Sell Stock with Cooldown

LeetCode 309 · Medium

The problem

You may buy and sell as many times as you like, but you hold at most one share at a time, and after selling you must wait one day before buying again.

prices = [1,2,3,0,2]   →  3     (buy 1, sell 2, cooldown, buy 0, sell 2)

The pattern

The second dimension here is not a position — it is which situation you are in.

The cooldown makes today's options depend on what you did yesterday, so a single "best profit so far" number is not enough. You need to know whether you are holding a share, whether you just sold, or whether you are free to act.

Three states cover everything:

HOLD — you own a share.
SOLD — you sold today, so tomorrow is a cooldown day.
REST — you own nothing and you are free to buy.

And the transitions follow directly from the rules:

        buy                 sell
REST ────────→ HOLD ────────────→ SOLD
  ↑              ↑ (do nothing)     │
  └──────────────────────────────────┘
              cooldown ends

\text{hold}_t = \max(\text{hold}_{t-1},\ \ \text{rest}_{t-1} - price_t)

\text{sold}_t = \text{hold}_{t-1} + price_t

\text{rest}_t = \max(\text{rest}_{t-1},\ \ \text{sold}_{t-1})

Read them in words:

hold — either you were already holding, or you were resting and bought today (paying the price).
sold — you must have been holding, and you sold today (receiving the price). There is no other way to be in SOLD.
rest — either you were already resting, or you sold yesterday and the cooldown has now passed.

That last line is where the cooldown lives. You can only reach REST from SOLD after a full day, which is exactly what "rest reads yesterday's sold" enforces.

The solution

PythonTypeScript

python

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0

        hold = -prices[0]        # bought on day 0
        sold = float('-inf')     # impossible before any sale
        rest = 0                 # doing nothing costs nothing

        for price in prices[1:]:
            prev_hold, prev_sold, prev_rest = hold, sold, rest

            hold = max(prev_hold, prev_rest - price)
            sold = prev_hold + price
            rest = max(prev_rest, prev_sold)

        return max(sold, rest)   # never end holding a share

function maxProfit(prices: number[]): number {
  if (!prices.length) return 0;

  let hold = -prices[0], sold = -Infinity, rest = 0;

  for (let i = 1; i < prices.length; i++) {
    const [pHold, pSold, pRest] = [hold, sold, rest];
    hold = Math.max(pHold, pRest - prices[i]);
    sold = pHold + prices[i];
    rest = Math.max(pRest, pSold);
  }

  return Math.max(sold, rest);
}

Snapshot all three before updating any of them. Every transition reads yesterday's values, so updating hold first and then using it to compute sold mixes today and yesterday. This is the bug in this problem, and it produces answers that are close but wrong.

sold starts at negative infinity because you cannot have sold before owning anything. Starting it at 0 would let the first rest = max(rest, sold) wrongly claim a completed sale.

hold starts at -prices[0] — buying costs money, so holding is a negative position until you sell.

Return max(sold, rest), never hold. Ending while still holding a share means money is tied up in an unsold asset, which is never optimal.

Trace

prices = [1, 2, 3, 0, 2]

day	price	hold	sold	rest
0	1	−1	−∞	0
1	2	−1	1	0
2	3	−1	2	1
3	0	1	−1	2
4	2	1	3	2

Answer max(3, 2) = 3 ✓. Day 3 is the interesting one: rest reached 2 because day 2's sold was 2, and that made buying at 0 give hold = 2 - 0 = wait, prev_rest - price = 1 - 0 = 1. The cooldown from the day-2 sale is what stops rest being 2 on day 3.

The general technique

When a constraint makes "the best so far" ambiguous, add a dimension for the situation you are in.

This is a state machine DP, and it is the same move as putting the hop count into the state in 4.21.6 Cheapest Flights. The states are the nodes; the transitions are the edges; you are finding the best path through time.

Drawing the state diagram before writing code is the whole method. With the diagram, the three lines write themselves. Without it, you will guess at the transitions.

Complexity

$O(n)$ time, $O(1)$ space.

The family

The stock problems are a ladder, and each rung adds state:

problem	states
Buy and Sell Stock	just track the minimum price — 4.6.1
Buy and Sell Stock II	greedy — take every rise
With Cooldown	hold / sold / rest
With a transaction fee	hold / free, subtracting the fee on sale
At most 2 transactions	hold and free × how many transactions used
At most k transactions	the same, generalised — $O(nk)$

They are one problem with different amounts of state, and seeing that is worth far more than solving each separately.

What the interviewer will push on

"Why can't you track a single best profit?" The cooldown makes today's options depend on yesterday's action, so the best-so-far number is ambiguous.

"Draw the state machine." Three states, four transitions. Do it before coding.

"Where is the cooldown enforced?" REST reads yesterday's SOLD, so a full day must pass.

"Why snapshot the variables?" Every transition reads yesterday's values.

"Why not return hold?" You would be holding an unsold share.

"What if there were a transaction fee instead?" Two states, subtracting the fee on sale.

One thing to volunteer: say that this is a state machine and that the second dimension is a situation rather than a position. That framing generalises to the whole stock family and to any problem with a "you cannot do X right after Y" rule.

Next: 4.24.4 Coin Change II — where the order of two loops decides whether you count combinations or permutations.

4.24.3 — Best Time to Buy and Sell Stock with Cooldown ​

The problem ​

The pattern ​

The solution ​

Trace ​

The general technique ​

Complexity ​

The family ​

What the interviewer will push on ​