309. Best Time to Buy and Sell Stock with Cooldown (Medium)

Problem

Given prices for a stock on consecutive days, maximize profit. You may make unlimited transactions but:

• You must sell the stock before buying again.
• After a sell, you must wait one day before buying again (cooldown).

Example

• prices = [1, 2, 3, 0, 2] → 3 (buy day 0, sell day 1, cooldown day 2, buy day 3, sell day 4)
• prices = [1] → 0

LeetCode 309 · Link · Medium

Approach 1: Recursive with state

At each day, you’re in one of three states: holding a stock, free (can buy), cooldown (can’t buy this day).

def max_profit(prices):
    n = len(prices)
    def f(i, holding, cooldown):
        if i == n:                                                   # L1: O(1) base case
            return 0
        best = f(i + 1, holding, False)                             # L2: skip today
        if holding:
            best = max(best, prices[i] + f(i + 1, False, True))    # L3: sell
        elif not cooldown:
            best = max(best, -prices[i] + f(i + 1, True, False))   # L4: buy
        return best
    return f(0, False, False)

Where the time goes, line by line

Variables: n = len(prices).

Line	Per-call cost	Times executed	Contribution
L1 (base case)	O(1)	once per leaf	O(1) each
L2-L4 (recursive branches)	O(1) work + up to 2 calls	O(2^n) call tree	O(2^n) ← dominates

Each state (i, holding, cooldown) can fan out into two calls. Without caching, identical states are recomputed across different branches.

Complexity

• Time: O(2^n), driven by the exponential call tree from L2-L4.
• Space: O(n) recursion depth.

Approach 2: Top-down memoized

from functools import lru_cache

def max_profit(prices):
    n = len(prices)
    @lru_cache(maxsize=None)                                         # L1: cache decorator
    def f(i, holding, cooldown):
        if i == n:                                                   # L2: O(1) base case
            return 0
        best = f(i + 1, holding, False)                             # L3: skip (O(1) with cache)
        if holding:
            best = max(best, prices[i] + f(i + 1, False, True))    # L4: sell (O(1) with cache)
        elif not cooldown:
            best = max(best, -prices[i] + f(i + 1, True, False))   # L5: buy (O(1) with cache)
        return best
    return f(0, False, False)

Where the time goes, line by line

Variables: n = len(prices).

Line	Per-call cost	Times executed	Contribution
L1 (lru_cache)	O(1)	1	O(1)
L2 (base case)	O(1)	once per leaf state	O(1) each
L3-L5 (cached calls)	O(1) per call	at most n * 2 * 2 = 4n states	O(n) ← dominates

The state space is n * 2 * 2 = 4n (day, holding bool, cooldown bool). Each state is computed once.

Complexity

• Time: O(n), driven by L3-L5 across at most 4n unique states.
• Space: O(n) for the memo table and recursion stack.

Approach 3: Bottom-up three-state DP (optimal)

Track three scalar states: hold (holding a stock), sold (just sold, must cooldown next day), rest (free to buy).

def max_profit(prices):
    if not prices:                                           # L1: O(1) guard
        return 0
    hold = -prices[0]                                       # L2: O(1) init: buy on day 0
    sold = 0                                                # L3: O(1) init
    rest = 0                                                # L4: O(1) init

    for i in range(1, len(prices)):                        # L5: O(n) loop
        prev_hold, prev_sold, prev_rest = hold, sold, rest # L6: O(1) snapshot
        hold = max(prev_hold, prev_rest - prices[i])       # L7: O(1) keep or buy from rest
        sold = prev_hold + prices[i]                        # L8: O(1) sell from hold
        rest = max(prev_rest, prev_sold)                    # L9: O(1) stay rest or from cooldown

    return max(sold, rest)                                  # L10: O(1) answer

Where the time goes, line by line

Variables: n = len(prices).

Line	Per-call cost	Times executed	Contribution
L1-L4 (init)	O(1)	1	O(1)
L5 (loop)	O(1) body	n - 1	O(n) ← dominates
L6-L9 (state transitions)	O(1)	n - 1	O(n)
L10 (answer)	O(1)	1	O(1)

Three scalars replace the full DP table. Each day’s transitions are O(1): L7 chooses between holding or buying (subtracts the buy price from rest); L8 locks in the sell; L9 absorbs the cooldown state.

Complexity

• Time: O(n), driven by L5 (the single loop).
• Space: O(1), just three scalars.

State machine

The three states are nodes in a DAG:

• rest → rest (do nothing)
• rest → hold (buy)
• hold → hold (do nothing)
• hold → sold (sell)
• sold → rest (cooldown expires)

Summary

Approach	Time	Space
Naive recursion	O(2^n)	O(n)
Memoized	O(n)	O(n)
Three-state scalar DP	O(n)	O(1)

State-machine DP is the right abstraction whenever you have “at each position, the set of things you could be doing is finite.” Best Time to Buy and Sell Stock IV (fixed K transactions) extends this pattern.

Test cases

# Quick smoke tests, paste into a REPL or save as test_309.py and run.
# Uses the canonical implementation (Approach 3: three-state scalar DP).

def max_profit(prices):
    if not prices:
        return 0
    hold = -prices[0]
    sold = 0
    rest = 0
    for i in range(1, len(prices)):
        prev_hold, prev_sold, prev_rest = hold, sold, rest
        hold = max(prev_hold, prev_rest - prices[i])
        sold = prev_hold + prices[i]
        rest = max(prev_rest, prev_sold)
    return max(sold, rest)

def _run_tests():
    # problem statement examples
    assert max_profit([1, 2, 3, 0, 2]) == 3
    assert max_profit([1]) == 0
    # edge: empty
    assert max_profit([]) == 0
    # always decreasing (never profitable to buy)
    assert max_profit([5, 4, 3, 2, 1]) == 0
    # always increasing (buy day 0, sell last day, but cooldown means we may skip)
    assert max_profit([1, 2, 3, 4, 5]) == 4
    # two-day window
    assert max_profit([1, 2]) == 1
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

Related data structures

• Arrays, input; state-machine transitions