Medium LeetCode 309 · 11 min read

Best Time to Buy and Sell Stock with Cooldown

1. Problem & Core Objective

Given daily prices, maximise profit with unlimited transactions, subject to: you may hold at most one share, and after selling you must wait one day before buying again (a one-day cooldown).

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

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

What's actually being tested: a state machine DP. The second dimension isn't an index into another sequence — it's which state you're in. Recognising that "2-D" can mean "indexed by state" is the transferable idea.

2. First-Principles Thought Process

The state is more than the day

Profit on day i depends on whether you're holding a share, and if not, whether you just sold (and are therefore in cooldown).

So three states:

State	Meaning
HOLD	currently own a share
SOLD	sold today — tomorrow is a cooldown
REST	own nothing and may buy

The transitions

hold[i] = max(hold[i-1],              stay holding
              rest[i-1] - prices[i])   buy today (only from REST, not SOLD)

sold[i] = hold[i-1] + prices[i]        sell today — must have been holding

rest[i] = max(rest[i-1],               keep resting
              sold[i-1])               yesterday's sale; cooldown now over

The cooldown is encoded in one place: hold can only be entered from rest, never from sold. That single restriction is the entire constraint, and it's why the SOLD state exists at all.

Why three states and not two

Without SOLD you couldn't distinguish "own nothing and free to buy" from "own nothing but just sold". The cooldown is exactly that distinction.

Base cases

hold[0] = -prices[0]     bought on day 0
sold[0] = 0              can't sell without owning
rest[0] = 0              did nothing

sold[0] = 0 rather than Integer.MIN_VALUE is defensible because it's unreachable in a way that never wins — but seeding it as impossible is safer, and I'd note which choice I made.

The answer

max(sold[n-1], rest[n-1]) — never hold, since ending while holding a share means unrealised value, which isn't profit.

3. Solution Paths

Approach 1 — Try every buy/sell combination (brute force)

Java

public int maxProfit(int[] prices) {
    return profit(prices, 0, false);
}

private int profit(int[] prices, int i, boolean holding) {
    if (i >= prices.length) return 0;

    int skip = profit(prices, i + 1, holding);                       // do nothing
    int act;
    if (holding) act = prices[i] + profit(prices, i + 2, false);     // sell, then cooldown
    else         act = -prices[i] + profit(prices, i + 1, true);     // buy

    return Math.max(skip, act);
}

Time O(2^n) · Space O(n) stack

Counter-questions on this approach

⭐ "Where is the cooldown expressed here?"

In the i + 2 after selling — it skips the next day entirely. That's the most direct encoding, and it's worth writing first because it makes the constraint obvious before the state machine abstracts it.

The state-machine version instead forbids SOLD → HOLD, which is the same rule expressed structurally rather than by index arithmetic.

⭐ "What's the state, and how many are there?"

(i, holding) — so 2n distinct states, not 2^n. Memoising on that pair collapses it immediately, and that memo table is the state machine.

"At n = 5000, how bad is the naive version?"

2^5000 — not a number worth naming. Even n = 40 would be hopeless.

Approach 2 — Three-state DP with arrays

Java

public int maxProfit(int[] prices) {
    int n = prices.length;
    if (n <= 1) return 0;

    int[] hold = new int[n], sold = new int[n], rest = new int[n];
    hold[0] = -prices[0];
    sold[0] = Integer.MIN_VALUE / 2;                 // impossible on day 0
    rest[0] = 0;

    for (int i = 1; i < n; i++) {
        hold[i] = Math.max(hold[i - 1], rest[i - 1] - prices[i]);
        sold[i] = hold[i - 1] + prices[i];
        rest[i] = Math.max(rest[i - 1], sold[i - 1]);
    }
    return Math.max(sold[n - 1], rest[n - 1]);
}

Trace — prices = [1,2,3,0,2]:

Day	Price	`hold`	`sold`	`rest`
0	1	−1	−∞	0
1	2	max(−1, 0−2) = −1	−1+2 = 1	max(0, −∞) = 0
2	3	max(−1, 0−3) = −1	−1+3 = 2	max(0, 1) = 1
3	0	max(−1, 1−0) = 1	−1+0 = −1	max(1, 2) = 2
4	2	max(1, 2−2) = 1	1+2 = 3	max(2, −1) = 2

max(sold[4], rest[4]) = max(3, 2) = 3 ✓

Time O(n) · Space O(n)

Counter-questions on this approach

⭐ "Why can hold only be entered from rest and not from sold?"

Because that is the cooldown. Selling on day i−1 puts you in SOLD, and buying on day i would violate the one-day wait.

rest[i] = max(rest[i-1], sold[i-1]) is what releases you: yesterday's sale becomes today's rest, and from rest you may buy tomorrow.

So the constraint lives in exactly one transition being absent. That's the payoff of the state-machine framing — the rule is structural rather than scattered through index arithmetic.

⭐ "Why Integer.MIN_VALUE / 2 rather than Integer.MIN_VALUE?"

Because sold[0] feeds into rest[1] = max(rest[0], sold[0]), and while that particular line doesn't add, a differently-arranged recurrence might. Halving leaves headroom so any accidental addition can't wrap to a large positive.

It's the same sentinel-arithmetic discipline as amount + 1 in Coin Change: pick an "impossible" value that survives the operations performed on it.

Setting sold[0] = 0 also works here, since day-0 profit of 0 is achievable by doing nothing — but then SOLD and REST mean the same thing on day 0, which muddies the invariant. I prefer the explicit impossibility.

⭐ "Why is the answer never hold[n-1]?"

Because holding a share at the end means you spent money and never realised the value. hold is always negative or represents an incomplete transaction.

Including it could only lower the max, but it would be conceptually wrong — the problem asks for realised profit.

"Why n <= 1 returns 0?"

With one price you can buy but never sell, so no profit is possible. And the loop starting at i = 1 wouldn't run, leaving max(sold[0], rest[0]) = max(−∞, 0) = 0 — actually correct, but the guard makes it explicit and avoids the sentinel appearing in the answer.

Approach 3 — Rolling variables (optimal)

Java

public int maxProfit(int[] prices) {
    int hold = -prices[0], sold = Integer.MIN_VALUE / 2, rest = 0;

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

        hold = Math.max(prevHold, prevRest - prices[i]);
        sold = prevHold + prices[i];
        rest = Math.max(prevRest, prevSold);
    }
    return Math.max(sold, rest);
}

Time O(n) · Space O(1)

Counter-questions on this approach

⭐ "Why snapshot all three before updating?"

Because each new value depends on the previous generation of the others. Updating hold first and then using it for sold would read today's value instead of yesterday's — computing a buy and a sell on the same day.

Same read-the-previous-generation discipline as Maximum Product Subarray's max snapshot and Bellman-Ford's array clone.

With three interdependent variables it's easier to get wrong than with two, which is why I'd write all three snapshots explicitly rather than trying to order the assignments cleverly.

"Why is rolling valid here?"

Each state reads only day i−1 — a fixed one-step window. Three scalars replace three arrays.

"Could the profit overflow?"

Prices are at most 1000 with 5000 days, so even an absurd alternating buy/sell caps profit around 2.5 × 10^6. Far inside int.

The only overflow risk is the sentinel, which is why it's MIN_VALUE / 2.

"How would you extend this to a k-day cooldown?"

Replace the single SOLD state with k cooldown states, or track the day you last sold. The transition graph grows but the shape is identical — which is the argument for framing it as a state machine rather than as ad-hoc index arithmetic.

Comparison

Approach	Time	Space	Notes
Recursion	`O(2^n)`	`O(n)` stack	State is `(i, holding)`
Three arrays	`O(n)`	`O(n)`	States made explicit
Rolling scalars	`O(n)`	`O(1)`	The answer

4. Why the Optimal Wins

The recursion explores 2^n buy/sell sequences over 2n distinct states.

The real content is the modelling: recognising that the second dimension is a state, not an index into another sequence, and that the cooldown is expressed as one missing transition.

The framing worth keeping:

Three states — HOLD, SOLD, REST. The cooldown is the absence of a SOLD → HOLD transition; you must pass through REST first. When the second dimension is a state rather than an index, "2-D DP" means a state machine.

5. Java Prerequisites

Three-state transitions

Java

hold = max(prevHold, prevRest - price);    // buy only from REST
sold = prevHold + price;                    // sell requires holding
rest = max(prevRest, prevSold);             // yesterday's sale is released

Snapshot all three before any assignment — each reads the previous generation.

Sentinel with headroom — Integer.MIN_VALUE / 2, so accidental addition can't wrap.

The answer excludes hold — ending with a share is unrealised value.

6. Interview Communication Guide

Clarifying questions: How many shares may I hold (one)? Is the cooldown one day (yes)? Unlimited transactions (yes)? Does the cooldown apply after buying too (no — only after selling)? Can I buy and sell on the same day (no — that's zero profit anyway)?

The pitch

"The day index alone isn't enough state. Profit depends on whether I'm holding a share, and if not, whether I just sold — because that triggers the cooldown.

So three states: HOLD, SOLD, and REST.

The transitions: I can keep holding or buy today; I sell only if I was holding; and I rest either by continuing to rest or by coming out of yesterday's sale.

The cooldown is encoded as one missing transition — HOLD can only be entered from REST, never from SOLD. That single restriction is the entire constraint, and it's why the SOLD state needs to exist separately from REST. Without it I couldn't distinguish 'own nothing and free to buy' from 'own nothing but just sold'.

The answer is max(sold, rest) at the end — never hold, because ending while holding a share is unrealised value, not profit.

Each state reads only the previous day, so three rolling scalars give O(n) time and O(1) space.

One implementation detail: I snapshot all three previous values before updating any of them. Each new value depends on yesterday's others, and updating hold first would let sold read today's value — computing a buy and a sell on the same day. With three interdependent variables that's easier to get wrong than with two.

And I seed sold at Integer.MIN_VALUE / 2 rather than MIN_VALUE, leaving headroom so any addition can't wrap to a large positive.

The framing generalises: if the cooldown were k days, I'd add k cooldown states. The transition graph grows but the shape doesn't change — which is the argument for modelling it as a state machine rather than as index arithmetic."

Edge cases to volunteer:

Input	Expected	Tests
`[1]`	0	Can't sell — loop never runs
`[1,2]`	1	One transaction
`[2,1]`	0	Decreasing — never buy
`[1,2,3,0,2]`	3	The worked example
`[1,2,4]`	3	Cooldown makes one big trade better than two
All equal prices	0	No profit available

Name [1,2,4]. Without the cooldown you'd take both trades for 1 + 2 = 3; with it, buying at 1 and selling at 4 also gives 3 — but a naive solution that ignores the cooldown and takes every rise would report 3 here and be wrong on longer inputs. [1,2,3,0,2] is the one where the cooldown actually costs you.

7. Follow-Up Questions — Modified Constraints

⭐ "What if there were a transaction fee instead of a cooldown?"

LeetCode 714. Two states suffice — HOLD and REST — with the fee subtracted on sale. Simpler, because no state is needed to remember when you sold.

That contrast is instructive: the cooldown needs a third state precisely because it depends on timing.

⭐ "What if the cooldown were k days?"

Replace SOLD with k sequential cooldown states, or track the last sale day. O(n · k) time. The state-machine framing makes this a mechanical extension.

"Limit the number of transactions to at most k."

LeetCode 188. Add a transaction-count dimension: dp[i][t][holding]. O(n · k) time and space, rolling to O(k). This is where the second dimension becomes a genuine count rather than a state label.

"Return the actual buy/sell days."

Track which transition won at each step. O(n) extra space, forfeiting the O(1) rolling — the usual trade.

"What if prices could be negative?"

Nothing breaks — the recurrence never assumes positivity. Buying at a negative price would be profitable, which is odd but handled.

"What if n were 10^6?"

The rolling version is O(n) time and O(1) space, so it scales directly. The array version would be 12 MB across three arrays, which is where rolling stops being cosmetic.