309. Best Time to Buy and Sell Stock with Cooldown

Model the trading rules as a three-state machine — hold, sold, and rest — and track only the rolling maximum profit for each state. The cooldown constraint collapses naturally into one forbidden transition.

● MediumState Machine DPRolling VariablesDynamic ProgrammingTypeScript

PROBLEM What we're solving

Given an array prices where prices[i] is the stock price on day i, find the maximum profit with unlimited transactions, subject to one rule: after you sell, you must skip exactly one day (the cooldown) before buying again. Concrete example: prices = [1, 2, 3, 0, 2] → best strategy is buy day 0 (price 1), sell day 2 (price 3, profit +2), cool down day 3, buy day 3 (price 0), sell day 4 (price 2, profit +2) → total profit = 3.

KEY IDEA State machine: three states, one forbidden arrow

Insight → at any day, you are in exactly one of three states: hold (own stock), sold (just sold today — tomorrow is cooldown), or rest (idle / cooled down — free to buy tomorrow). The cooldown forces sold → rest → hold; you cannot go directly sold → hold. Track the maximum profit achievable in each state as rolling variables — no 2-D table needed.

RECIPE Three rolling maxima, updated in order

0 · Initialise. Day 0: hold = -prices[0] (bought), sold = -∞ (impossible), rest = 0 (did nothing).
1 · Snapshot previous values. Save prevHold, prevSold, prevRestso simultaneous updates don't clobber each other.
2 · Update hold. hold = max(prevHold, prevRest - prices[i]) — keep holding, or buy today (can only buy from the rest state, enforcing cooldown).
3 · Update sold. sold = prevHold + prices[i]— sell today, so profit jumps by today's price.
4 · Update rest. rest = max(prevRest, prevSold)— stay idle, or absorb yesterday's sell (the cooldown day itself earns nothing).
5 · Answer. max(sold, rest, 0) — we never end holding; take the best of sold and rest.

Classic confusion → forgetting to snapshot the previous values before the loop body. If you write hold = max(hold, rest - p) then sold = hold + p in sequence, the second line reads the already-updated hold — a silent bug that inflates profits. Always capture prevHold / prevSold / prevRest first.

COST Complexity & alternatives

Naive (try all transactions)

O(2ⁿ)

Exponential branching on every day.

State machine DP

O(n) time · O(1) space

Three rolling scalars; no array or table needed.

A naïve DP would allocate a 3×n table, but since each state on day i only depends on day i-1, we can collapse to three scalars. Time is a single O(n) pass; space is O(1).

Pattern transfer → the same state-machine skeleton solves all Stock with Constraint variants: at most k transactions (add a transaction counter dimension), transaction fee (subtract fee on sell), and at most 2 transactions (unroll to 4 states). The cooldown version is the cleanest illustration of the pattern.

RUN IT State machine: hold / sold / rest

prices =

step 0 / 17

STARTPrices: [1, 2, 3, 0, 2]. Track three states: hold (own stock), sold (just sold), rest (cooldown, can buy next day). Init: hold = -1, sold = -∞, rest = 0.

1function maxProfit(prices: number[]): number {
2  // Three states:
3  //   hold  = max profit while currently holding stock
4  //   sold  = max profit on the day we just sold (triggers cooldown)
5  //   rest  = max profit while on cooldown / idle (can buy next day)
6▶  let hold = -prices[0]; // bought on day 0
7▶  let sold = -Infinity;  // impossible to have sold before day 0
8▶  let rest = 0;          // started with nothing, did nothing
9 
10  for (let i = 1; i < prices.length; i++) {
11    const prevHold = hold;
12    const prevSold = sold;
13    const prevRest = rest;
14 
15    // keep holding OR buy from rest (rest -> hold, NOT sold -> hold, so cooldown enforced)
16    hold = Math.max(prevHold, prevRest - prices[i]);
17    // sell today (hold -> sold)
18    sold = prevHold + prices[i];
19    // stay idle OR recover from yesterday's sale (sold -> rest)
20    rest = Math.max(prevRest, prevSold);
21  }
22 
23  // We never end while holding; answer is the better of sold and rest
24  return Math.max(sold, rest, 0);
25}

1d02d13d20d32d4

State

-1

hold

-∞

sold

rest

active day / hold or rest updatehold transition computedsold transition computedfinal answer

slowfast

TYPESCRIPT The solution, annotated

maxProfitWithCooldown.ts
function maxProfit(prices: number[]): number {
  // Three states:
  //   hold  = max profit while currently holding stock
  //   sold  = max profit on the day we just sold (triggers cooldown)
  //   rest  = max profit while on cooldown / idle (can buy next day)
  let hold = -prices[0]; // bought on day 0
  let sold = -Infinity;  // impossible to have sold before day 0
  let rest = 0;          // started with nothing, did nothing

  for (let i = 1; i < prices.length; i++) {
    const prevHold = hold;
    const prevSold = sold;
    const prevRest = rest;

    // keep holding OR buy from rest (rest -> hold, NOT sold -> hold, so cooldown enforced)
    hold = Math.max(prevHold, prevRest - prices[i]);
    // sell today (hold -> sold)
    sold = prevHold + prices[i];
    // stay idle OR recover from yesterday's sale (sold -> rest)
    rest = Math.max(prevRest, prevSold);
  }

  // We never end while holding; answer is the better of sold and rest
  return Math.max(sold, rest, 0);
}

Reading it block by block

Lines 2–4 — the state model. The three variables represent mutually exclusive states. hold = best profit while you own a share. sold = best profit on days you just executed a sale (tomorrow is forced cooldown). rest = best profit while idle or cooling down.

Lines 5–7 — base case (day 0). If we buy on day 0, hold = -prices[0] (paid that price). We cannot have sold yet so sold = -Infinity. We haven't done anything so rest = 0.

Lines 9–11 — snapshot. All three transitions read from yesterday's state. Capturing prevHold, prevSold, prevRest before mutating is essential — forgetting this is the most common bug.

Lines 13–14 — hold transition. Math.max(prevHold, prevRest - prices[i]): either we were already holding (no action), or we buy today. Crucially we can only buy from the rest state, not the sold state — that single restriction enforces the entire cooldown rule.

Line 16 — sold transition. prevHold + prices[i]: the only way to reach soldis by selling. We add today's price to the best profit from holding.

Line 18 — rest transition. Math.max(prevRest, prevSold): either we were already resting/idle, or we transition from yesterday's sold (the cooldown day itself: we earned nothing extra, but the cash from the sale is now available for future buys).

Line 22 — answer. We never want to end holding stock. The answer is Math.max(sold, rest, 0): the better of having just sold or being idle, with a floor of 0 for a declining market.

Complexity → O(n) time — one pass through prices. O(1) space — only three scalars regardless of input length; the full O(3n) table collapses because each day depends only on the previous day.

INTERVIEWFollow-ups they'll ask

"Return the actual trade sequence?" Track a parent pointer array recording which state each day transitioned from; backtrack from the final state to reconstruct buy/sell days.
"What if the cooldown is k days (not 1)?" Replace the single rest scalar with a queue of length k; on each day shift the queue and the oldest sold becomes available.
"Add a transaction fee?" Subtract the fee on every sell: sold = prevHold + prices[i] - fee. The rest of the transitions are unchanged.
"At most k transactions?" Add a transaction dimension: hold[k], sold[k] — each sell increments the transaction counter. (LC 188.)
"What's the brute force?" Try all valid buy/sell sequences with DFS: O(2ⁿ). The DP improves this to O(n) by collapsing overlapping subproblems into three states.

OPTIMAL State Machine DP

maxProfitWithCooldown.ts
function maxProfit(prices: number[]): number {
  // Three states:
  //   hold  = max profit while currently holding stock
  //   sold  = max profit on the day we just sold (triggers cooldown)
  //   rest  = max profit while on cooldown / idle (can buy next day)
  let hold = -prices[0]; // bought on day 0
  let sold = -Infinity;  // impossible to have sold before day 0
  let rest = 0;          // started with nothing, did nothing

  for (let i = 1; i < prices.length; i++) {
    const prevHold = hold;
    const prevSold = sold;
    const prevRest = rest;

    // keep holding OR buy from rest (rest -> hold, NOT sold -> hold, so cooldown enforced)
    hold = Math.max(prevHold, prevRest - prices[i]);
    // sell today (hold -> sold)
    sold = prevHold + prices[i];
    // stay idle OR recover from yesterday's sale (sold -> rest)
    rest = Math.max(prevRest, prevSold);
  }

  // We never end while holding; answer is the better of sold and rest
  return Math.max(sold, rest, 0);
}

ALT 1 Brute force — recurse over every buy/sell/cooldown decision

O(2ⁿ) time · O(n) space

Walk day by day and branch on the only choices available: if not holding, either buy today or skip; if holding, either sell today (then jump two days ahead for the mandatory cooldown) or keep holding. Return the best profit over all branches.

approach-2.ts
function maxProfit(prices: number[]): number {
  function dfs(day: number, holding: boolean): number {
    if (day >= prices.length) return 0;

    // Option 1: do nothing today
    const skip = dfs(day + 1, holding);

    let act: number;
    if (holding) {
      // sell today, then cooldown forces us to day + 2
      act = prices[day] + dfs(day + 2, false);
    } else {
      // buy today
      act = -prices[day] + dfs(day + 1, true);
    }

    return Math.max(skip, act);
  }

  return dfs(0, false);
}

Note → Every day spawns two recursive calls, so the tree is O(2ⁿ) and explodes past ~25 prices. The state is fully captured by (day, holding), so memoising on that pair — or rolling the three states forward with O(1) variables — collapses it to O(n).

MNEMONIC The one-liner

"Hold can only be reached from Rest — that single rule locks in the cooldown. Sold flows into Rest, Rest flows into Hold."

TRIGGERS When you see _ → reach for _

"sell with cooldown" / "skip one day after selling"	state machine: hold / sold / rest
unlimited transactions + constraint after selling	three rolling scalars + snapshot-before-update
stock problem with a cooldown or fee	extend 2-state hold/nothold to include the restricted transition
"at most k" or "at most 2" transactions	same state machine + transaction counter dimension

SKELETON The reusable shape

skeleton.ts
let hold = -prices[0];
let sold = -Infinity;
let rest = 0;

for (let i = 1; i < prices.length; i++) {
  const ph = hold, ps = sold, pr = rest;
  hold = Math.max(ph, pr - prices[i]); // keep | buy from rest
  sold = ph + prices[i];               // sell (was holding)
  rest = Math.max(pr, ps);             // idle | come off cooldown
}

return Math.max(sold, rest, 0);

FLASHCARDS Tap to flip

Name the three states in the cooldown stock problem.

hold (own stock), sold (just sold — next day is cooldown), rest (idle / cooling down — free to buy tomorrow).

tap to flip

1 / 8

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

For prices = [1, 2, 3, 0, 2], what is the maximum profit?

QUESTION 02

Which transition correctly enforces the cooldown rule?

QUESTION 03

Why must you snapshot the previous state values before the loop body updates?

QUESTION 04

What is the time and space complexity of the rolling-variable solution?

QUESTION 05

After the loop ends, why do we return Math.max(sold, rest, 0) instead of Math.max(hold, sold, rest)?

QUESTION 06

For prices = [1] (single day), what does the algorithm return?

QUESTION 07

If you added a transaction fee of 1, how would the sold transition change?

QUESTION 08

#309 · Best Time to Buy and Sell Stock with CooldownModel three states — holding, just-sold (cooldown), and resting — with transitions enforcing the one-day cooldown. Three rolling variables capture the full state machine in O(n) time.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA State machine: three states, one forbidden arrow

RECIPE Three rolling maxima, updated in order

COST Complexity & alternatives

RUN IT State machine: hold / sold / rest

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL State Machine DP

ALT 1 Brute force — recurse over every buy/sell/cooldown decision

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _