Best Time to Buy and Sell Stock with Cooldown Solution

Problem

You have a list of daily stock prices. You may buy and sell as many times as you want, but you can only hold one share at a time, and after every sale you must sit out one day (the cooldown) before buying again. Find the maximum profit you can earn.

Input: prices = [1, 2, 3, 0, 2]
Output: 3
Explanation: Buy on day 0 (price 1), sell on day 2 (price 3), cooldown on day 3, buy on day 3 (price 0), sell on day 4 (price 2) — profit = 2 + 2 = 3. Wait — buy day 0 sell day 2 = 2 profit, then buy day 3 sell day 4 = 2 profit, but cooldown after day-2 sell means can't buy day 3. Actually: buy day 0, sell day 1, cooldown day 2, buy day 3, sell day 4 = 1 + 2 = 3.

Counter-example: prices = [1] → 0 (can't complete any transaction with a single day).

Intuition

The challenge is the cooldown: you can't buy on the day immediately after a sale. This creates a dependency between decisions three days apart, which rules out a simple greedy approach. The key insight is to track not just whether you're holding stock, but which state you're in — holding, just sold (cooldown), or free to buy — so each transition follows directly from the previous day's state.

Approach 1 — State Machine DP

Model three explicit states for each day and compute the maximum profit reachable in each:

held — you own a share today
sold — you sold today (tomorrow is forced cooldown)
rest — you're not holding and not in cooldown (free to buy)

Initialize day 0: held = -prices[0] (paid to buy), sold = 0, rest = 0.
For each subsequent day, compute all three states from the previous day's values.
held[i] is either yesterday's held (do nothing) or yesterday's rest minus today's price (buy).
sold[i] is yesterday's held plus today's price (sell the share you were holding).
rest[i] is either yesterday's rest (do nothing) or yesterday's sold (come off cooldown).
Answer is max(sold[-1], rest[-1]) — never end while holding.

1def maxProfit(prices: list[int]) -> int:
2    n = len(prices)
3    if n < 2:
4        return 0
5
6    held = [0] * n
7    sold = [0] * n
8    rest = [0] * n
9
10    held[0] = -prices[0]  # paid to buy on day 0
11
12    for i in range(1, n):
13        held[i] = max(held[i - 1], rest[i - 1] - prices[i])  # keep holding or buy from rest
14        sold[i] = held[i - 1] + prices[i]                    # sell what we were holding
15        rest[i] = max(rest[i - 1], sold[i - 1])              # cooldown expires or stay resting
16
17    return max(sold[-1], rest[-1])

Time: O(n) — single pass through all prices.
Space: O(n) — three arrays of length n for the three states.

Approach 2 — Space-Optimized DP

Each state on day i depends only on the previous day's values, so three scalar variables replace the three arrays.

Initialize prev_held = -prices[0], prev_sold = 0, prev_rest = 0.
For each remaining price, compute the three new values from the saved previous values.
Store the new values back into the three variables.
Return max(prev_sold, prev_rest).

1def maxProfit(prices: list[int]) -> int:
2    if len(prices) < 2:
3        return 0
4
5    prev_held = -prices[0]
6    prev_sold = 0
7    prev_rest = 0
8
9    for price in prices[1:]:
10        curr_held = max(prev_held, prev_rest - price)  # keep holding or buy from rest
11        curr_sold = prev_held + price                  # sell what we were holding
12        curr_rest = max(prev_rest, prev_sold)          # cooldown expires or stay resting
13        prev_held, prev_sold, prev_rest = curr_held, curr_sold, curr_rest
14
15    return max(prev_sold, prev_rest)

Time: O(n) — same single pass.
Space: O(1) — only six scalar variables regardless of input size.

Complexity Summary

Approach	Time	Space	When to use
State Machine DP	O(n)	O(n)	When clarity matters more than memory; easier to debug
Space-Optimized DP	O(n)	O(1)	Production code or memory-constrained environments

Common Mistakes

Buying on the cooldown day — forgetting that after selling you must skip a day before buying; the state machine enforces this by only allowing buys from the rest state, never from sold.
Updating variables in place — computing prev_held = max(prev_held, prev_rest - price) then using the already-updated prev_held for curr_sold; always compute all three new values before overwriting the old ones.
Returning held in the answer — including max(held, sold, rest) at the end; ending while holding means you never sold, so held should never be the answer.
Wrong initial state for held — initializing held[0] = 0 instead of -prices[0]; buying on day 0 costs money, so the profit starts negative.
Off-by-one on the cooldown — thinking cooldown is 2 days instead of 1; after selling on day i, the earliest you can buy is day i+2 (one forced rest day).

Best Time to Buy and Sell Stock with Cooldown — Solution