Best Time to Buy and Sell Stock with Cooldown — 3-State Machine DP

Problem Statement#

You are given an array prices where prices[i] is the price of a given stock on the i-th day. Find the maximum profit you can achieve. You may complete as many transactions as you like with one important constraint: after you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).

Constraints:

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

Example 1:

Input:  prices = [1, 2, 3, 0, 2]
Output: 3
Explanation: Buy day 1 (1), sell day 2 (2), cooldown day 3, buy day 4 (0), sell day 5 (2).
             Profit = (2-1) + (2-0) = 3.

Example 2:

Input:  prices = [1]
Output: 0
Explanation: Only one day — cannot buy and sell.

Example 3:

Input:  prices = [6, 1, 3, 2, 4, 7]
Output: 6
Explanation: Buy day 2 (1), sell day 5 (4), cooldown day 6... wait, or buy day 2 (1), sell day 6 (7), profit=6.

Why This Problem Matters#

Stock with Cooldown (LC 309) is the most elegant extension in the stock series because the cooldown constraint adds a new state to the machine without increasing complexity. The resulting 3-state system — holding, sold (in cooldown), and resting — clearly shows how DP state machines model temporal constraints.

The key difference from Stock II: in Stock II, the "buy" transition reads from the "not holding" state of the previous day. In Stock with Cooldown, the "buy" transition must read from the "resting" state two days ago (skipping one cooldown day). This single structural change captures the full constraint.

Amazon and Google ask this problem to see whether candidates can correctly model time-delayed state transitions — a skill that appears in real-world scheduling and resource allocation algorithms.

The Core Insight#

3-state machine:

1. holding: Currently holding a stock. Best profit = maximum of (keep holding from yesterday) or (buy today from resting state two days ago — or more precisely, from the "rest" state yesterday, which means we were cooling down before that).
2. sold: Just sold stock today. Now in 1-day cooldown. Cannot buy tomorrow.
3. resting: Not holding and not in cooldown. Free to buy tomorrow.

Transitions:

holding = max(holding, resting - price)   # keep holding, or buy (from rest state)
sold    = holding + price                  # sell today (must have been holding)
resting = max(resting, sold)              # rest (cooldown ended) or continue resting

Wait — but the holding update uses yesterday's resting, while sold and resting use yesterday's holding and sold. We need to snapshot previous values:

prev_holding = holding
prev_sold    = sold
prev_resting = resting
 
holding = max(prev_holding, prev_resting - price)
sold    = prev_holding + price
resting = max(prev_resting, prev_sold)

Base cases:

• holding = -infinity (haven't bought yet)
• sold = -infinity (haven't sold yet — can't be in cooldown without selling)
• resting = 0 (start of the problem — not holding, not in cooldown)

Answer: max(sold, resting) — maximum profit when not holding at the end (could be in cooldown or resting).

Building the DP Solution#

Alternative 2-variable formulation: Some implementations track only hold and cash, with cash representing the "can buy tomorrow" state, and the buy transition using cash from 2 days ago. This requires remembering the previous cash value:

hold = float('-inf')
cash = 0
prev_cash = 0  # cash from 2 days ago (before cooldown)
 
for price in prices:
    new_hold = max(hold, prev_cash - price)  # buy from 2-days-ago cash
    new_cash = max(cash, hold + price)       # sell or rest
    prev_cash = cash                          # shift the 2-day window
    hold, cash = new_hold, new_cash

3-variable formulation (more explicit):

def maxProfit(prices):
    holding = float('-inf')
    sold = float('-inf')
    resting = 0
 
    for price in prices:
        prev_holding, prev_sold, prev_resting = holding, sold, resting
        holding = max(prev_holding, prev_resting - price)
        sold    = prev_holding + price
        resting = max(prev_resting, prev_sold)
 
    return max(sold, resting)

Visual Dry Run#

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

Initial state: holding = -inf, sold = -inf, resting = 0

Answer: max(sold, resting) = max(3, 2) = 3

State transitions shown as a table:

Optimized Solution#

Python#

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        # Three states: holding, sold (cooldown), resting (free to buy)
        holding = float('-inf')  # not yet bought
        sold    = float('-inf')  # not yet sold (can't be in cooldown yet)
        resting = 0              # starting state: free to buy, no profit yet
 
        for price in prices:
            # Snapshot previous day's state before updating
            prev_holding, prev_sold, prev_resting = holding, sold, resting
 
            # Keep holding, or buy today using resting state (not from sold — cooldown!)
            holding = max(prev_holding, prev_resting - price)
 
            # Sell today — must have been holding
            sold    = prev_holding + price
 
            # Rest: either continue resting, or the cooldown just ended (sold yesterday)
            resting = max(prev_resting, prev_sold)
 
        # Final answer: not holding (either in cooldown from today's sell, or resting)
        return max(sold, resting)

JavaScript#

var maxProfit = function(prices) {
    let holding = -Infinity;
    let sold    = -Infinity;
    let resting = 0;
 
    for (const price of prices) {
        const prevHolding = holding;
        const prevSold    = sold;
        const prevResting = resting;
 
        holding = Math.max(prevHolding, prevResting - price);
        sold    = prevHolding + price;
        resting = Math.max(prevResting, prevSold);
    }
 
    return Math.max(sold, resting);
};

Complexity Analysis#

Common Mistakes#

1. Allowing buy directly from sold (yesterday's sell) instead of resting. After selling, there is a 1-day cooldown — you cannot buy the very next day. The buy transition must use resting (the state after cooldown has passed), not sold (still in cooldown). Using sold directly removes the cooldown constraint.

2. Updating states without snapshotting previous values. If you update holding first and then compute sold using the just-updated holding, you read same-day values. You must snapshot all three state values before any updates to ensure transitions are between days, not within the same day.

3. Initializing sold = 0 instead of -infinity. sold = 0 means "sold for free — profit 0." This state is unreachable on day 0 (you haven't bought anything yet). Initializing to -infinity correctly marks it as unreachable.

4. Returning only resting at the end. After the last day, you could be in the sold state (just sold today) or the resting state (not holding and not in cooldown). The maximum of both is the answer. Returning only resting misses the case where selling on the last day is optimal.

5. Forgetting that resting absorbs sold. The resting transition is resting = max(resting, sold) — cooldown ends and you transition from sold to resting. After one day of cooldown, resting absorbs the sold profit. Forgetting this causes resting to never accumulate the sell profits from previous transactions.

Interview Tips#

• Draw the 3-state diagram: Three nodes (holding, sold, resting) with labeled transitions. This is the clearest way to explain the cooldown constraint visually.
• Emphasize the buy constraint: "The key change from unlimited transactions is that the buy transition uses resting (cooldown has ended), not sold (still cooling down)."
• Snapshot before updating: "I'll save all three previous-day values before computing the new ones — otherwise updates bleed across the same day."
• Explain the 2-day delay intuitively: "After selling, I spend one day in cooldown. So the buy on day i uses the state from day i-2 at the earliest — which is what resting captures."
• For the 2-variable version: "Some implementations track hold, cash, and prev_cash — where prev_cash is the 2-day-ago cash. Both formulations are equivalent."

Follow-up Questions#

Q: What if the cooldown is 2 days instead of 1? Add another state cooldown1 between sold and resting: the sell transitions to cooldown1, then cooldown1 transitions to resting the next day. The buy transition still uses resting.

Q: How does this differ from Stock II? Stock II: buy transition uses yesterday's cash (not-holding state directly after sell). Cooldown: buy transition uses resting — the state after one cooldown day has passed since selling.

Q: Can the cooldown state be modeled without a separate variable? Yes — use a 2-day lookback on the cash variable. Track cash and prev_cash (2 days ago): hold = max(hold, prev_cash - price). This is an equivalent 2-variable formulation.

Q: What if there is both a cooldown and a transaction fee? Combine both: sold = prev_holding + price - fee and resting = max(prev_resting, prev_sold). Both constraints modify only specific transitions — they compose cleanly.

Key Takeaways#

• Three states: holding (stock in hand), sold (cooldown — cannot buy tomorrow), resting (free to buy).
• Buy transition: holding = max(holding, resting - price) — uses resting, NOT sold.
• Sell transition: sold = holding + price — from holding state.
• Rest transition: resting = max(resting, sold) — absorbs sold profit after cooldown day.
• Always snapshot all three state values before updating — cross-day transitions must use yesterday's values.
• Final answer: max(sold, resting) — the maximum profit when not currently holding a stock.
• The cooldown constraint is captured entirely by which state the buy transition reads from — a beautiful example of how DP state design encodes temporal constraints.