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

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

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)

function maxProfit(prices: number[]): number {
    const n = prices.length;
    function f(i: number, holding: boolean, cooldown: boolean): number {
        if (i === n) return 0;                                           // L1: O(1) base case
        let best = f(i + 1, holding, false);                            // L2: skip today
        if (holding)
            best = Math.max(best, prices[i] + f(i + 1, false, true));  // L3: sell
        else if (!cooldown)
            best = Math.max(best, -prices[i] + f(i + 1, true, false)); // L4: buy
        return best;
    }
    return f(0, false, false);
}

func maxProfit(prices []int) int {
    max := func(a, b int) int { if a > b { return a }; return b }
    n := len(prices)
    var f func(i, holding, cooldown int) int
    f = func(i, holding, cooldown int) int {
        if i == n { return 0 }                                  // L1: O(1) base case
        best := f(i+1, holding, 0)                              // L2: skip today
        if holding == 1 {
            best = max(best, prices[i]+f(i+1, 0, 1))           // L3: sell
        } else if cooldown == 0 {
            best = max(best, -prices[i]+f(i+1, 1, 0))          // L4: buy
        }
        return best
    }
    return f(0, 0, 0)
}

final class Solution {
    func maxProfit(_ prices: [Int]) -> Int {
        func solve(_ day: Int, _ holding: Bool) -> Int { if day >= prices.count { return 0 }; if holding { return max(solve(day + 1, true), prices[day] + solve(day + 2, false)) }; return max(solve(day + 1, false), -prices[day] + solve(day + 1, true)) }
        return solve(0, 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.

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)

function maxProfit(prices: number[]): number {
    const n = prices.length;
    const memo: Map<string, number> = new Map();
    function f(i: number, holding: boolean, cooldown: boolean): number {
        if (i === n) return 0;                                           // L2: O(1) base case
        const key = `${i},${holding},${cooldown}`;
        if (memo.has(key)) return memo.get(key)!;                       // L1: O(1) cache lookup
        let best = f(i + 1, holding, false);                            // L3: skip
        if (holding)
            best = Math.max(best, prices[i] + f(i + 1, false, true));  // L4: sell
        else if (!cooldown)
            best = Math.max(best, -prices[i] + f(i + 1, true, false)); // L5: buy
        memo.set(key, best);
        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.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

final class Solution {
    func maxProfit(_ prices: [Int]) -> Int {
        var memo: [String: Int] = [:]
        func solve(_ day: Int, _ holding: Bool) -> Int { if day >= prices.count { return 0 }; let key = "\(day):\(holding)"; if let value = memo[key] { return value }; let value = holding ? max(solve(day + 1, true), prices[day] + solve(day + 2, false)) : max(solve(day + 1, false), -prices[day] + solve(day + 1, true)); memo[key] = value; return value }
        return solve(0, false)
    }
}

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

function maxProfit(prices: number[]): number {
    if (prices.length === 0) return 0;                              // L1: O(1) guard
    let hold = -prices[0];                                          // L2: O(1) init: buy on day 0
    let sold = 0;                                                   // L3: O(1) init
    let rest = 0;                                                   // L4: O(1) init
    for (let i = 1; i < prices.length; i++) {                      // L5: O(n) loop
        const prevHold = hold, prevSold = sold, prevRest = rest;   // L6: O(1) snapshot
        hold = Math.max(prevHold, prevRest - prices[i]);            // L7: O(1) keep or buy
        sold = prevHold + prices[i];                                // L8: O(1) sell from hold
        rest = Math.max(prevRest, prevSold);                        // L9: O(1) stay or from cooldown
    }
    return Math.max(sold, rest);                                    // L10: O(1) answer
}

func maxProfit(prices []int) int {
    max := func(a, b int) int { if a > b { return a }; return b }
    if len(prices) == 0 { return 0 }              // L1: O(1) guard
    hold := -prices[0]                            // L2: O(1) init: buy on day 0
    sold, rest := 0, 0                            // L3+L4: O(1) init
    for i := 1; i < len(prices); i++ {            // L5: O(n) loop
        ph, ps, pr := hold, sold, rest            // L6: O(1) snapshot
        hold = max(ph, pr-prices[i])              // L7: O(1) keep or buy from rest
        sold = ph + prices[i]                     // L8: O(1) sell from hold
        rest = max(pr, ps)                        // 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)

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

final class Solution {
    func maxProfit(_ prices: [Int]) -> Int {
        var hold = Int.min / 4, sold = 0, rest = 0
        for price in prices { let previousSold = sold; sold = hold + price; hold = max(hold, rest - price); rest = max(rest, previousSold) }
        return max(sold, rest)
    }
}

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()

function maxProfit(prices: number[]): number {
    if (prices.length === 0) return 0;
    let hold = -prices[0], sold = 0, rest = 0;
    for (let i = 1; i < prices.length; i++) {
        const ph = hold, ps = sold, pr = rest;
        hold = Math.max(ph, pr - prices[i]);
        sold = ph + prices[i];
        rest = Math.max(pr, ps);
    }
    return Math.max(sold, rest);
}

console.assert(maxProfit([1, 2, 3, 0, 2]) === 3);
console.assert(maxProfit([1]) === 0);
console.assert(maxProfit([]) === 0);
console.assert(maxProfit([5, 4, 3, 2, 1]) === 0);
console.assert(maxProfit([1, 2, 3, 4, 5]) === 4);
console.assert(maxProfit([1, 2]) === 1);
console.log("all tests pass");

package main

import "fmt"

func maxProfit(prices []int) int {
    max := func(a, b int) int { if a > b { return a }; return b }
    if len(prices) == 0 { return 0 }
    hold, sold, rest := -prices[0], 0, 0
    for i := 1; i < len(prices); i++ {
        ph, ps, pr := hold, sold, rest
        hold = max(ph, pr-prices[i])
        sold = ph + prices[i]
        rest = max(pr, ps)
    }
    return max(sold, rest)
}

func main() {
    if maxProfit([]int{1, 2, 3, 0, 2}) != 3 { panic("fail") }
    if maxProfit([]int{1}) != 0 { panic("fail") }
    if maxProfit([]int{}) != 0 { panic("fail") }
    if maxProfit([]int{5, 4, 3, 2, 1}) != 0 { panic("fail") }
    if maxProfit([]int{1, 2, 3, 4, 5}) != 4 { panic("fail") }
    if maxProfit([]int{1, 2}) != 1 { panic("fail") }
    fmt.Println("all tests pass")
}

Arrays, input; state-machine transitions

Dynamic Programming, the state and transition model for reusing answers to overlapping subproblems.
State Compression, the memory reduction tactic for keeping only states the next transition needs.

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

Problem

Try it yourself

Approach 1: Recursive with state

Approach 2: Top-down memoized

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

State machine

Summary

Test cases

Related data structures

Related concepts