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)

Constraints:

1 <= prices.length <= 5000
0 <= prices[i] <= 1000

Plain-English Restatement: You have a magical time machine and you know the price of a specific stock for the next $N$ days. You can trade it to make money, but there are rules:

You can't hold more than one share at a time. You have to sell your current share before you can buy another.
When you sell, you are forced to take a "cooldown" day off. You cannot buy anything the very next day. Find the maximum possible profit you can make.

Brute Force Approach: At every day, you have a choice. If you hold a stock, you can sell or wait. If you don't hold a stock, you can buy or wait. You could draw out a massive decision tree exploring every valid combination of actions over the $N$ days.

Time Complexity: $O(2^n)$ . Each day gives you roughly 2 choices, leading to an exponential number of possible trading sequences.
Why it's wasteful: If you arrive at Day 5 with $10 in your pocket and holding 0 shares, it does not matter whether you made that $10 through one trade or two trades. The brute force approach calculates the future possibilities for Day 5 multiple times. DP collapses all these identical states together.

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.

ELI5 Analogy: Imagine you are playing a video game character that can only be in one of three stances: "Holding a shield" (HOLD), "Just dropped the shield" (SOLD), or "Walking normally" (REST). You can't just spawn a shield; you have to transition between these stances legally. You want to finish the game with the highest score possible. At any given step, your best score in a specific stance depends entirely on the best scores from the legal stances you could have been in one step prior.

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.

Code Walkthrough

Initial States:
- hold = -prices[0]: On day 0, if we decide to end the day in the HOLD state, we must have bought the stock, lowering our profit to -prices[0].
- sold = float('-inf'): We can't possibly sell on day 0, so this state is impossible. We set it to negative infinity so it's never chosen by a max() comparison.
- rest = 0: If we do nothing on day 0, our profit is 0.
The Loop: for price in prices[1:]: starts from day 1 to the end.
Snapshotting: prev_hold, prev_sold, prev_rest = hold, sold, rest. We freeze yesterday's optimal values. If we didn't do this, updating hold first would corrupt the calculation for sold (which relies on yesterday's hold, not today's).
Hold Transition: hold = max(prev_hold, prev_rest - price). You either kept the stock from yesterday (prev_hold), or you were resting yesterday and bought today (prev_rest - price).
Sold Transition: sold = prev_hold + price. You must have been holding yesterday, and you sold it at today's price.
Rest Transition: rest = max(prev_rest, prev_sold). You either were already resting, or you sold yesterday and are now forced to rest.

Complexity Derivation

Time Complexity: $O(n)$ . We loop through the prices array exactly once. Inside the loop, we perform a constant $O(1)$ number of additions and maximum comparisons.
Space Complexity: $O(1)$ . We do not allocate an array of size $N$ . We only maintain a few integer variables (hold, sold, rest, and their prev_ equivalents) to track the state transitions.

Edge Cases

Prices length is 1: Handled perfectly by the early return or the loop just not running. Returns max(sold, rest) which will be 0.
Prices are monotonically decreasing: e.g., [5, 4, 3, 2, 1]. The hold state will update to the lowest negative price, but sold and rest will remain 0 (or negative). max(sold, rest) returns 0 correctly because it's better not to trade at all.

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 ​

Code Walkthrough ​

Complexity Derivation ​

Edge Cases ​

The family ​

What the interviewer will push on ​