Problem Overview — Buy and Sell with a Mandatory 1-Day Gap
LeetCode 309 gives you an array of stock prices where prices[i] is the price on day i. You can buy and sell unlimited times, but after selling you must sit out at least one day before buying again — the cooldown. Your goal is to maximize total profit.
The cooldown separates this from Stock II (LeetCode 122), where you can buy immediately after selling. Here, selling on day i means you cannot buy on day i+1. You must wait for day i+2 at the earliest. This single constraint is what forces you to track an extra state.
Brute force tries every combination of buy and sell days, which grows exponentially. The key insight is that on any given day, you are in exactly one of three states: holding stock, having just sold (in cooldown), or at rest with no stock and not cooling down. Tracking these three states lets you solve it in O(n) time and O(1) space.
- Input: prices array, e.g., [1, 2, 3, 0, 2]
- Output: maximum profit, e.g., 3
- You can buy and sell unlimited times
- After each sale, you must skip at least 1 day before buying again
- You cannot hold multiple stocks simultaneously
- Goal: maximize total profit across all transactions
Three-State Machine — Hold, Sold, and Rest
The state machine has three nodes: hold (you currently own stock), sold (you just sold today, so tomorrow is cooldown), and rest (you do not own stock and are not in cooldown, free to buy). Each day you transition between these states based on what action you take.
From hold, you can either continue holding (stay in hold) or sell (move to sold). From sold, you are forced into rest the next day — you cannot buy immediately. From rest, you can either stay at rest (do nothing) or buy stock (move to hold). The transitions define exactly which prior state each new state depends on.
These three states are mutually exclusive and exhaustive — every possible situation is captured. The DP values represent the maximum cash on hand in each state at the end of each day. The answer is the maximum of sold and rest after the last day, since holding stock at the end is never optimal.
Why Three States
The cooldown constraint adds a third state beyond the usual hold/cash split: the "sold" state forces a 1-day gap before the next buy. This is what distinguishes LeetCode 309 from Stock II and Stock with Fee — both of which work cleanly with just two states.
State Transitions — The Three Recurrences
The three recurrences are: hold = max(hold, rest - price); sold = hold + price; rest = max(rest, sold). Process them in this exact order each day, using the previous day's values on the right-hand side. The "hold" recurrence says you either keep holding from yesterday or buy today from the rest state (not sold, because you cannot buy during cooldown).
The "sold" recurrence is simply yesterday's hold value plus today's price — you sell whatever you were holding. The "rest" recurrence says you either stay at rest from yesterday or transition out of the sold state from yesterday (cooling down period ends). The chaining sold → rest is what enforces the mandatory gap.
Because sold feeds into next day's rest, and rest feeds into hold, the cooldown gap is automatically embedded in the transitions. You never need a special index offset or a look-back of two days — the state machine handles it implicitly through the sold → rest → hold chain.
- 1Initialize: hold = -prices[0], sold = 0, rest = 0
- 2For each day i from 1 to n-1, save previous hold, sold, rest
- 3new_hold = max(prev_hold, prev_rest - prices[i]) — keep holding or buy from rest
- 4new_sold = prev_hold + prices[i] — sell what was held yesterday
- 5new_rest = max(prev_rest, prev_sold) — stay resting or come off cooldown
- 6Update hold, sold, rest to new values
- 7Return max(sold, rest) after processing all days
Why Three States and Not Two — The Two-State Breakdown
With only two states — hold and cash — the recurrence for hold would be hold = max(hold, cash[i-1] - price). This requires looking back two days (cash[i-2]) rather than one, because you cannot use yesterday's cash directly after a sale. Two-state solutions with a look-back of two work but require careful index handling and easily lead to off-by-one errors.
The three-state version is cleaner precisely because it makes the cooldown explicit. The sold state is a named placeholder for "cash from yesterday's sale that is not yet usable." Instead of reaching back two days in a two-state model, you just read from the rest state, which was populated from sold the previous day.
Both approaches are O(n) time and O(1) space, so the difference is conceptual clarity. In an interview, the three-state version is easier to derive from scratch: draw the state machine, label the edges with actions, write one recurrence per node. The two-state version requires intuition about indexing that is harder to justify on the spot.
Two-State Alternative
Alternatively, use two states with hold = max(hold, cash[i-2] - price), accessing two days back. This works but requires handling the base case cash[-1] = 0 and is more error-prone during derivation. The three-state version is cleaner and avoids all index gymnastics.
Walk-Through Example — prices = [1, 2, 3, 0, 2]
Start with hold = -1, sold = 0, rest = 0 (buy on day 0 costs 1 unit). On day 1 (price=2): new_hold = max(-1, 0-2) = -1; new_sold = -1+2 = 1; new_rest = max(0, 0) = 0. State: hold=-1, sold=1, rest=0. On day 2 (price=3): new_hold = max(-1, 0-3) = -1; new_sold = -1+3 = 2; new_rest = max(0, 1) = 1. State: hold=-1, sold=2, rest=1.
On day 3 (price=0): new_hold = max(-1, 1-0) = 1; new_sold = -1+0 = -1; new_rest = max(1, 2) = 2. State: hold=1, sold=-1, rest=2. The rest value of 2 comes from the sold=2 profit locked in on day 2. On day 4 (price=2): new_hold = max(1, 2-2) = 1; new_sold = 1+2 = 3; new_rest = max(2, -1) = 2. State: hold=1, sold=3, rest=2.
Answer = max(sold, rest) = max(3, 2) = 3. The optimal strategy is buy at 1, sell at 3 (profit 2), cool down on day 3, buy at 0, sell at 2 (profit 2) — but the total is 3, not 4, because buying at 0 after selling at 3 is not possible without the cooldown. The actual optimal is buy at 1, sell at 3 (day 0 to day 2), skip day 3, buy at 0 on day 3 is during cooldown — so buy at 0, sell at 2 is profit 2; total is 3 from buy at 1 sell at 3 only.
- 1Day 0 (price=1): hold=-1, sold=0, rest=0 — buy on day 0
- 2Day 1 (price=2): hold=-1, sold=1, rest=0 — sell at 2 for profit 1
- 3Day 2 (price=3): hold=-1, sold=2, rest=1 — sell at 3 for profit 2
- 4Day 3 (price=0): hold=1, sold=-1, rest=2 — buy at 0 using rest profit of 1
- 5Day 4 (price=2): hold=1, sold=3, rest=2 — sell at 2 for total profit 3
- 6Answer = max(sold=3, rest=2) = 3
Code Walkthrough — Python and Java
The Python implementation uses three variables and processes them with saved previous values to avoid overwriting mid-update. Initialize hold = -prices[0], sold = 0, rest = 0. For each subsequent price, compute new_hold, new_sold, new_rest from the saved previous values, then overwrite. Return max(sold, rest). Time O(n), space O(1).
The Java implementation mirrors the Python logic. Use int hold = -prices[0], sold = 0, rest = 0. In the loop, save prevHold and prevSold before updating. Compute hold = Math.max(hold, rest - prices[i]); sold = prevHold + prices[i]; rest = Math.max(rest, prevSold). Note that rest does not need a saved copy because it is read before being updated. Return Math.max(sold, rest).
Edge cases: single day — no transactions possible, return 0 (hold=-prices[0], sold=0, rest=0; answer = max(0,0) = 0, correct). Two days — either sell on day 1 (profit = prices[1]-prices[0] if positive, else 0) or do nothing. The state machine handles both without special casing.
Simultaneous Updates Required
Update all three states simultaneously — save prev_hold and prev_sold before computing new values. If you update hold first and then use the updated hold to compute sold, you get wrong answers. The recurrences must all read from the same previous day's state.